Поиск указателя i, где A [i] = i

Question

Учитывая отсортированный массив различных целых чисел A [1,. , , , n], вы хотите узнать, есть ли индекс i, для которого A [i] = i. Дайте алгоритм разделения и покоя, который выполняется во времени O (log n).

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

modifiedBinSearch(a[1],a[n]){ 

int i = a.length/2; 

if(a[i]==i) return i; 

if(i>a[i]) return ModifiedBinSearch(a[1],a[i]); 

else return ModifiedBinSearch(a[i], a[n]); 

} 

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

Answer 1

Ваш альгоритм не работает, int i = a.length/2; это всегда одно и то же значение, размер массива a не изменяется.

Вам нужно запомнить как минимум две переменные и массив. Две переменные: «min» и «max», чтобы знать границы массива, для которых вы рекурсивный двоичный поиск.

Подумайте об этом как о публикации в словаре.

Например, он имеет 1024 страницы, вы ищете слово «ягода».

Вы открываете его на странице 512, и вы найдете «мама», поэтому она должна быть в пределах от 0 - 512.

Так вы смотрите на 256, и вы найдете «алгоколя» -> оно должно быть в пределах 256 - 512

и т.д.

Эти два значения, что минимальное и максимальное, и вы должны передать их в качестве параметров в вашем рекурсивном методе.

Answer 2

Если ваш псевдо-код на самом деле означает, что мы передаем массив функции, и мы можем получить его подмассив в O(1) время, то время сложность действительно O(log n), так как размер массива получает (approximatly) в два раза меньше, после каждого шага ,

Answer 3

Определим A как входной массив, а N - длина этого массива.

Сначала необходимо отметить, что массив отсортирован и целые числа являются отчетливое. Это означает, что с учетом двух индексов (i, j), где i < j, затем A[i]+1 <= A[j]. В свою очередь это означает, что A[i]-i <= A[i+1]-(i+1).

Из этого замечания можно заключить, с помощью рекурсии, что массив B определяется как:

For i in (0..N-1) B[i] = A[i]-i 

Есть также упорядоченный массив.

Ваш псевдокод - это просто бинарный поиск, чтобы найти, есть ли 0 в B. Индекс этого значения является индексом, который вы хотите найти.

Binary-search имеет сложность O[log(n)].

Примечания:Почему я говорю, что псевдокод является двоичным поиском значения 0?

Просто замените условие:

• a[i] == i с: a[i]-i == 0
• i > a[i] с: a[i]-i < 0

Примечание 2

псевдокод не обрабатывать случай, когда значение отсутствует.

Answer 4

Я заранее извиняюсь за смехотворный псевдокод. Технически ваш алгоритм работает в O(logn) времени, потому что половина списка отключается каждый раз (разделить на 2 каждый раз, поэтому мы получаем базу данных 2). Однако, как указывает ливик, a.length всегда то же самое, поэтому вы никуда не денусь. Вам нужно передать индексы в качестве параметров.

func(a, lo, hi) 
    len = hi - lo + 1 
    mid = len/2 + lo 
    switch len, a[mid] > mid 
     case 1, _: a[lo] = lo ? lo : -1 
     case _, t: func(a, lo, mid - 1) 
     case _, _: func(a, mid, hi) 

func(arr, 0, arr.length - 1)