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/>';
// > не найдено
// > не найдено


PHP Алгоритм up: просмотров: 100