Рекурсивный бинарный поиск на PHP

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

Но это далеко не оптимальный алгоритм поиска если речь идет о упорядоченном массиве.

Если у нас упорядоченный массив, то можно применить бинарный поиск (он же двоичный поиск)!
Бинарный поиск имеет сложность по времени O(lg n) (lg - сокращенная запись двоичного логарифма Log2 N), то есть обратный экспоненциальному росту двойки (степень двойки вообще важный момент в информатике, можете почитать вот это).

Уже из этого можно сделать вывод, то это крайне быстрый алгоритм, даже по сравнению с линейным O(n).

Для сравнения количество операций линейного и логарифмического алгоритма при n=65536 (2^16).
n = 65536
lg n = 16

Как наиболее простой пример возьмем числовой массив, но это может быть любой массив, главное, что бы существовал словарь соответствий, то есть некий источник, который определяет порядок последовательности.
Для строк например таким словарем может быть алфавит.

Суть алгоритма довольно проста и наверное понятна из названия.
Например кто то загадал число от 1 до 100 (пусть это будет 26), и вам надо понять какое это число задав наименьшее количество вопросов.
Как тут действовать наиболее оптимально? Вероятно отсекать максимально возможные (половинные) числовые интервалы.

Сначала мы спросим: "Загаданное число больше или меньше 50?"
Так как 26 < 50 мы понимаем, что искомое число лежит в интервале от 1 до 50. Это 50? Нет. -> 1-49.

Далее мы спрашиваем: "Загаданное число больше 25?".
Так как 26 > 25 мы понимаем, что число лежит в интервале от 25 до 49. Это 25? Нет. -> 26-49.

    Последующие ответы на вопросы:
  • 26 < 37. 37? Нет. ->26-36.
  • 26 < 31. 31? Нет. ->26-30.
  • 26 < 28. 28? Нет. ->26-27.
  • Это 27? Нет. Значит это 26.

Запишем сначала в виде кода с циклом.

function binarySearch($m, $x)
{
    $s = 0;
    $f = count($m)-1;
    
    while($s <= $f)
    {
        $q = floor(($s+$f)/2);
        
        if($m[$q] == $x)
        {
            return $q;
        }
        elseif($m[$q] > $x)
        {
            $f = $q-1;
        }
        else
        {
            $s = $q+1;
        }
    }
    
    return 'notFound';
}

На вход мы подаем массив m и искомое значение x.
После чего сразу определяем искомый интервал поиска через s-стартовую позицию и f-финальную позицию, так как это первая итерация, интервал будет равен длине самого массива.

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

В цикле первым делом определяем q-середину в искомом интервале.
Проверяем является ли q индексом искомого значения, если нет, то мы проверяем больше или меньше значение в индексе q относительно искомого значения x.
Если m[q] больше x, то ограничиваем искомый интервал сверху, и отсекаем половину массива, делая конечной точкой f=q-1.
Если m[q] меньше x, то ограничиваем искомый интервал снизу делая конечной точкой s=q+1.

Теперь запишем код рекурсивного бинарного поиска.

function recBinarySearch($m, $x, $s, $f)
{
    if ($s > $f)
    {
        return 'notFound';
    }
    
    $q = floor(($s+$f)/2);
    
    if($m[$q] == $x)
    {
        return $q;
    }
    elseif($m[$q] > $x)
    {
        return recBinarySearch($m, $x, $s, $q-1);
    }
    else
    {
        return recBinarySearch($m, $x, $q+1, $f);
    }
}

Если в вашей программе поиск в массиве является частым явлением, то есть смысл предварительно его отсортировать (если он не является остортированным) и использовать бинарный поиск вместо линейного.


comments powered by Disqus