PHP: Алгоритм бинарный поиск
Поиск значения в массиве с помощью алгоритма «Бинарный поиск» / «Двоичный поиск».
Входной массив должен быть отсортирован. Проверка начинается с середины. После каждой проверки исключается половина значений из проверяемого массива.
Сложность: O(log n)
function binSearch( $list, $val ) { $lowIndex = 0; $hightIndex = sizeof( $list ) - 1; while( $lowIndex <= $hightIndex ) { $middleIndex = round( ( $lowIndex + $hightIndex ) / 2 ); $test = $list[ $middleIndex ]; if( $test == $val ) { return $middleIndex; } else if( $test > $val ) { $hightIndex = $middleIndex - 1; } else { $lowIndex = $middleIndex + 1; } } return 'не найдено'; } $sampleList = [ 4, 8, 15, 16, 23, 42 ]; foreach( $sampleList as $val ) { echo binSearch( $sampleList, $val ) .'<br/>'; } // > 0 // > 1 // > 2 // > 3 // > 4 // > 5 echo binSearch( $sampleList, -1 ) .'<br/>'; echo binSearch( $sampleList, 50 ) .'<br/>'; // > не найдено // > не найдено
Комментарии