Бинарный поиск

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

function binarySearch($needle, $array) {
  $low = 0;
  $high = count($array) - 1;
  while ($low <= $high) {
    $middle = floor(($low + $high) / 2);
    if ($array[$middle] == $needle) {
      return $middle;
    }
    if ($array[$middle] > $needle) {
      $high = $middle - 1;
    } else {
      $low = $middle + 1;
    }
  }
  return null;
}

комментарии (0)