close

Алгоритм бинарного поиска (Binary Search) в PHP: объяснение, шаги и пример

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

Шаги:

  1. Инициализируйте диапазон поиска: начните с выбора диапазона поиска от первой позиции left  до последней позиции right  массива.
  2. Найдите среднюю точку: вычислите среднюю точку, усредняя left и правые позиции; это средняя точка диапазона поиска.
  3. Сравнить значения: Сравните значение в средней точке с целевым значением.
  4. Обработать результат сравнения: если значение в средней точке соответствует целевому значению, вернуть эту позицию. Если значение в средней точке меньше целевого значения, обновите левую позицию до средней + 1 для поиска правой половины. Если значение в средней точке больше целевого значения, обновите правую позицию до середины- 1 для поиска в левой половине.
  5. Повтор: Повторяйте шаги со 2 по 4, пока не будет найдено значение или не останется элементов для проверки left > right.

Преимущества и недостатки

Преимущества:

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

Недостатки:

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

Пример: двоичный поиск для нахождения значения 12 в отсортированном массиве в PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Пояснение к примеру

  1. Мы начинаем с начального диапазона поиска от первой позиции left = 0 до последней позиции right = 6  массива.
  2. Среднюю точку(mid) вычисляем, усредняя левую и правую позиции; mid = 3. Значение в середине равно 12.
  3. Мы сравниваем значение в mid(12) с целевым значением(12) и находим совпадение, поэтому возвращаем позицию 3.
  4. Алгоритм завершается, и мы выводим результат «Значение 12 найдено в позиции 3».