Алгоритм поиска в отсортированном массиве

Бинарный поиск — один из самых эффективных и широко используемых поисковых алгоритмов, и все программисты должны иметь его в своем арсенале. Он используется для поиска целевого значения в массиве и работает только с отсортированным массивом, будь то по возрастанию или по убыванию, причина этого заключается в том, как он работает.

В начале поиска объявляем два указателя. Мы помещаем первый в начальный индекс массива, а другой - в последний индекс массива. И то, и другое, начало и конец.

int start = 0, end = array[array.length - 1];

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

int middle = (start + end) / 2;

Но может возникнуть ситуация, когда значение выражения (начало + конец) превышает предел типа данных. Тогда это может быть не идеально. Итак, лучшая альтернатива - сделать следующее

int middle = start + (end - start) / 2;

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

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

if (target < array[middle]) {
    end = middle - 1;
} else if (target > array[middle]) {
    start = middle + 1;
}

Возьмем число 22 в 7-м индексе в качестве целевого элемента. Поскольку 22 больше 14, у нас теперь меньше область поиска с начальным указателем в индексе 5.

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

while (start <= end) {
    int middle = start + (end - start) / 2;
    if (target < array[middle]) {
        end = middle - 1;
    } else if (target > array[middle]) {
        start = middle + 1;
    } else {
        return middle;
    }
}

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

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