Алгоритм нахождения любого i, так что array [i] равен i

Question

У меня есть задание от моего профессора CS:

Найти, за O (logn) время, если в заданном предварительно отсортированном массиве различных целых чисел есть индекс i, так что массив [i] = я.Докажите, что время O (logn).

Обновление: Целые числа могут быть отрицательными, 0 или положительными.

Хорошо, поэтому я немного боролся с этим.Моя идея такова:

Используя бинарный поиск, мы можем быть уверены, что такого значения нет слева от среднего элемента, если array [mid] <= startindex, где mid - индекс среднего элемента,и startindex - начало массива. </p>

Соответствующее правило для правой половины массива - это массив [mid]> = startindex + цифра, где переменные, как указано выше, и цифра - это число элементов справа от середины..

Это не похоже на O (logn), так как в худшем случае мне приходится перебирать все это, верно?Может кто-нибудь подсказать мне в правильном направлении или сказать, что это работает?

Есть идеи, как я могу формально доказать это?Я не прошу однозначного ответа, больше помогу понять.

В C:

int _solve_prob_int(int depth, int start, int count, int input[])
    {
    if(count == 0)
        return 0;
    int mid = start + ((count - 1) / 2);
    if(input[mid] == mid)
        return 1;

    if(input[mid] <= start && input[mid] >= start + count)
        return 0;

    int n_sub_elleft = (int)(count - 1) / 2;
    int n_sub_elright = (int)(count) / 2;

    if(input[mid] <= start)
        return _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);

    if(input[mid] >= start + count)
        return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input);

    return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input) ||
            _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);
    }

Тестовый пример:

Sorted args: 1 2 3 4 5 6 7 8 9 10 11 12 : 
Start: 0, count: 12, mid: 5 value: 6
    Start: 0, count: 5, mid: 2 value: 3
        Start: 0, count: 2, mid: 0 value: 1
            Start: 1, count: 1, mid: 1 value: 2
        Start: 3, count: 2, mid: 3 value: 4
            Start: 4, count: 1, mid: 4 value: 5
    Start: 6, count: 6, mid: 8 value: 9
        Start: 6, count: 2, mid: 6 value: 7
            Start: 7, count: 1, mid: 7 value: 8
        Start: 9, count: 3, mid: 10 value: 11
            Start: 9, count: 1, mid: 9 value: 10
            Start: 11, count: 1, mid: 11 value: 12

выше моя программа запускается с некоторым выводом в соответствии с тем, как она искала.Со списком от 1 до 12 он поворачивается вокруг индекса 5, определяя, что может быть значение между 0-4 и индексами 0-4.Он также определяет, что может быть значение между 6-11 и индексами 6-11.Таким образом, я приступаю к поиску их обоих.Это неправильно?

Answer 1

Целые числа различаются и сортируются.

С учетом того, что array[i] = i у вас есть array[i] - i = 0.

Для каждого j array[j] - j <= 0, а для j> i у вас есть array[j] - j >= 0, потому что j меняются на 1 на каждом шаге, а массив [j] изменяется как минимум на 1 (разные и отсортированные числа).

Итак, слева это <=0, справа это >= 0.

Используя дихотомию, вы легко можете найти правильное положение в O(log n).

---

Обратите внимание, что вам нужно найти только один элемент, а не все. В вашем примере все элементы работают, но вам нужен только один из них. Если вы хотите распечатать их все это будет O(n) ..

Answer 2

Думайте о бинарном поиске, как о поиске слова в словаре.Вы можете начать с открытия книги точно по центру словаря и посмотреть, находится ли слово вверху страницы до, после или равно слову, которое вы ищете.Если это после, вы делите вторую половину словаря на две части и проверяете середину этой половины.Посмотрев на верх страницы, вы сузили область поиска примерно до четверти словаря.Вы продолжаете этот процесс, пока не обнаружите, что слово находится где-то на странице, которую вы просматриваете.Затем вы используете подобный процесс, чтобы найти слово на этой странице.

Этот процесс не O (n), потому что вам не нужно было смотреть каждое слово на каждой странице, даже в самом худшем случаесценарий.Это O (log n), потому что с каждым шагом вы могли удалять примерно половину словаря как , а не , содержащее искомое слово.

Редактировать

Извините, я неправильно понял исходную проблему.

В этом случае ключом является распознавание так называемого «принципа дырки в пиджоне», который гласит, что в один пиджон можно вписать только столько пиджонов.дырки, так как у вас есть дырки, чтобы соответствовать им. (Оставьте это на усмотрение академии, чтобы придумать название для такой простой идеи!)

Рассмотрим следующий случай:

0 1 2 3 4 5 6

Здесь, все array[i] равны i, поэтому, когда вы впервые начнете бинарный поиск, вы сразу получите положительный ответ.

Теперь давайте уберем число изbottom:

0 1 3 4 5 6

Когда вы выполните бинарный поиск, вы обнаружите, что array[3] > 3, и вы можете правильно сделать вывод, что никакое значение выше этой точки разворота не может составить array[i] == i.Это потому, что список упорядочен и уникален, поэтому вы не можете получить такие комбинации:

0 1 3 4 5 5 6
0 1 3 4 6 5 7

Как только array[i] определено больше i, просто нетдостаточно чисел между i и любым заданным n, чтобы следующий элемент в массиве приблизился к i.Аналогично, если вы определили, что array[i] меньше i, у вас недостаточно «пробелов», чтобы «догнать» до i при взгляде на начало массива.

Следовательно, на каждом шаге вы можете корректно исключить половину массива и, подобно просмотру словаря, определить, есть ли array[i] == i за O (log n) времени.

Answer 3

Это проблема бинарного поиска с ключом, который не указан .В вопросе OP ключ находится в середине!Вот и все, ищите средний элемент в каждом подмассиве.

Псевдокод решения с помощью двоичного поиска:

    while (low and high don't meet)
        mid = (low + high) / 2
        if (arr[mid] < mid)
            high = mid - 1
        else if (arr[mid] > mid)
            low = mid + 1
        else // we found it!
            return mid;
    // end while
    return -1; // indicates there is no such i

Answer 4

Ваша интуиция права использовать бинарный поиск; твой анализ нет. Помните, что это отсортированный список, поэтому в условиях бинарного поиска вам нужно искать МАКСИМАЛЬНОЕ из записей журнала (n).

Answer 5

public static int fixedPoint(int[] array, int start, int end) {

    if (end < start || start < 0 || end >= array.length) {
        return -1;
    }
    int midIndex = start +(end-start)/ 2;
    int midValue = array[midIndex];
    if (midValue == midIndex) {//trivial case
        return midIndex;
    }
    // if there are duplicates then we can't conclude which side (left or right) will
    // have the magic index. so we need to search on both sides
    //but, we can definitely exclude few searches.
    // take the example of the array : 
    //   0   1  2  3  4  5                        6  7  8  9   10 -> indices
    // -10, -5, 2, 2, 2, 3(midVal, midIndex = 5), 4, 7, 9, 12, 13 -> array element
    // here, midValue < midIndex, but we can't say for sure which side to exclude
    // as you can see there are two such magic indices. A[2] = 2 and A[7] = 7. so
    // we need to search both sides
    // since midValue < midIndex, then we can be sure that between index can't be
    // between index number midValue and midIndex-1

    /* Search left */
    int leftIndex = Math.min(midIndex - 1, midValue);
    int left = fixedPoint(array, start, leftIndex);
    if (left >= 0) {
        return left;
    }

    /* Search right */
    int rightIndex = Math.max(midIndex + 1, midValue);
    int right = fixedPoint(array, rightIndex, end);

    return right;
}

public static int fixedPoint(int[] array) {
    return fixedPoint(array, 0, array.length - 1);
}

Answer 6

Array B[i] = A[i]-i НЕ МОЖЕТ быть отсортировано, даже если A [i] отсортировано, но имеет дубликаты:

Рассмотрим этот пример:

i: 0 1 2 3 4
A: 1 1 2 4 4

B [0] = A [0] -0 = 1, B [1] = A [1] -1 = 0, ...

B: 1 0 0 1 0

Answer 7

, так как массив A отсортирован.A [i]> = A [i-1] +1 => A [i] -i> = A [i-1] - (i-1), пусть B [i] = A [i] -i,B [] - это отсортированный массив, в котором можно искать B [x] == 0 в течение времени lgn, используя двоичный поиск.

Answer 8

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

При рассмотрении среднего элемента, есть 3 случая. Первый - это, конечно, массив [i] == i, и в этом случае алгоритм завершается. В двух других случаях мы можем отбросить сам элемент, а также примерно половину ввода.

Теперь, если array [i]> i, возможно ли, чтобы индекс массива (i) «догонял» значения массива при движении вправо? Имейте в виду, отсортированные различные свойства значений массива.