Разработка и анализ алгоритма

Question

Я застрял в задаче, мне нужно решить проблему, здесь:

Написать алгоритм, который находит индекс i в массиве таким образом, что A[i] = i когда 0<=i<=n-1, если нет такого индекс нашел возвращение -1

Я сделал этот вопрос в O(n) время, но мои ребята говорят, что это может быть сделано за меньшее время некоторые где около O(lg(n))

может кто-нибудь поможет мне найти лучшее решение ?? Если да, ответьте на этот пост. Просьба ответить на этот пост .. Thanks

Answer 1

Если массив отсортирован, вы можете найти его в O(lg(n)) с помощью binary search. В противном случае это потребует O(n).

Answer 2

Вы должны сделать binary search на массиве. Вы пропустили очень важную часть описания проблемы - массив должен быть отсортирован заранее.

Answer 3

Если массив не отсортирован, это невозможно. Я предполагаю, что вы ищете детерминированный, не вероятностный алгоритм. Предположим, что существует алгоритм «Alg», который решает проблему, посещая ячейки O (log (n)) массива. Пусть V (I) - множество ячеек, которые посещают Alg на заданном входе I. Также предположим, что ответ на вход I1 равен -1, а Alg возвращает -1 правильно. Теперь измените одну из ячеек I1, которая не находится в V (I1), и снова передайте ее Alg. Конечно, Alg возвращает -1 снова, что не является правильным ответом.