Глубокое понимание бинарного поиска и его крайних случаев

алгоритм

Двоичный поиск — это эффективный алгоритм поиска отсортированных последовательностей со средней временной сложностью lg(n).

Упорядоченные последовательности можно разделить на монотонно неубывающие последовательности, такие как 1, 2, 3, 3, 3, 5, и монотонно не возрастающие последовательности, такие как 5, 3, 3, 3, 2, 1.

То есть в последовательности могут появляться повторяющиеся значения, но величина значений может изменяться только в одну сторону.

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

найти первое вхождение

В качестве примера возьмем монотонную неубывающую последовательность.

Идея: когда значение в середине больше или равно целевому значению, переместите правую границу влево; только когда значение в середине явно меньше целевого значения, пассивно переместите левую границу вправо, чтобы правую границу можно максимально сдвинуть влево.

Поскольку деление языка Java (C, C++, Python и т. д.) автоматически округляется в меньшую сторону, среднее положение mid будет смещено к левому краю слева, поэтому правое = среднее, а не правое = среднее — 1. Поскольку до тех пор, пока левое и правое не равны, правое = среднее будет смещено влево от исходного правого, что гарантирует непрерывное уменьшение диапазона.

Ниже приведена типичная ситуация для последнего цикла: целевое значение равно 3. Правый указатель пропускает позицию, большую или равную 3, до первых 3. В это время mid равен левому из-за округления в меньшую сторону. , обнаружено, что среднее значение at равно 2, что меньше целевого значения, поэтому левое = среднее + 1, перемещенное в правое положение.

Наконец, левое и правое равны, цикл завершается, а позиция — это позиция, в которой впервые появляется целевое значение (если целевое значение существует).

/**
 * @author: Wray Zheng
 * @date: 2018-04-06
 */
public static void binarySearchFirst(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int mid;

    while (left < right) {
        mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

Позвольте мне поговорить об этом здесь, почему состояние в то время как<, вместо<=. С одной стороны, мы хотим судить, является ли конечное левое положение целевым значением вне цикла, а с другой стороны, если условие цикла допускает левое = правое, то конечное среднее = левое = правое, и если это происходит быть целевым значением, то право всегда будет равно середине, оно больше не будет двигаться влево и попадет в бесконечный цикл.

Найдите последнее вхождение

Идея: когда значение в середине меньше или равно целевому значению, переместите левую границу вправо; только когда значение в середине явно больше целевого значения, пассивно переместите правую границу влево, чтобы левую границу можно максимально сдвинуть вправо.

Хотя деление самой Java автоматически округляется в меньшую сторону, мы можем добавить единицу к делимому перед выполнением деления, что эквивалентно округлению в большую сторону. вправо Переместите, чтобы сузить область поиска.

Ниже приведен случай последнего цикла, целевое значение также равно 3, левый указатель пропускает позицию, меньшую или равную 3, до последних 3, середина округляется вверх, равная правому, в это время значение среднего равно 5, что выше целевого. Значение большое, поэтому правое = среднее - 1, переход в левое положение.

Затем левое и правое равны, цикл завершается, и эта позиция является последним вхождением целевого значения.

/**
 * @author: Wray Zheng
 * @date: 2018-04-06
 */
public static void binarySearchLast(int[] arr, int target) {
    int left = 0;
    int right = ar.length - 1;
    int mid;

    while (left < right) {
        mid = left + (right - left + 1) / 2;
        if (arr[mid] > t) right = mid - 1;
        else left = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

Потому что последние левые и правые равны, так что судитеarr[left] == targetа такжеarr[right] == targetэквивалентны.

Для монотонно не возрастающих последовательностей

Я считаю, что после приведенного примера мы можем проанализировать ситуацию с монотонной невозрастающей последовательностью по той же логике.

Код приведен непосредственно ниже, не вдаваясь в подробности.

/**
 * @author: Wray Zheng
 * @date: 2018-04-06
 */
public static void binarySearchFirst(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int mid;

    while (left < right) {
        if (arr[mid] > t) left = mid + 1;
        else right = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

public static void binarySearchLast(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int mid;

    while (left < right) {
        if (arr[mid] < t) right = mid - 1;
        else left = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

Статьи по Теме

Loading Likes...
Категории