Дан упорядоченный по возрастанию массив различных целых чисел $% A[1…n]: A[1] < A[2] < … < A[n]$%. Постройте алгоритм, проверяющий за время $%O(logn)$%, найдётся ли такое $%i$%, что $%A[i]=i$%.

задан 28 Ноя '15 22:38

1

Возьмите простой двоичный поиск и попытайте его немного модифицировать. Если не смогли догадаться, возьмите конкретный массив из 100 чисел, удовлетворяющий условиям и попытайтесь там найти искомое $%i$%, просветление наступит быстро.

(28 Ноя '15 22:42) Trumba
1

@a2g: если вычесть из каждого элемента массива его номер, то получится неубывающая последовательность. Тогда задача будет состоять в поисках нуля, а это осуществляется методом половинного деления.

(28 Ноя '15 23:14) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×131
×129
×86
×76
×35

задан
28 Ноя '15 22:38

показан
372 раза

обновлен
28 Ноя '15 23:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru