Статьи

Алгоритм недели: бинарный поиск

Март 14, 2019

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

Базовая реализация бинарного поиска

 

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

Бинарный поиск - базовая реализация

 

Реализация

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

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

$list = array(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144);
$x = 55;
 
function binary_search($x, $list, $left, $right) 
{
	if ($left > $right)
		return -1;
 
	$mid = ($left + $right) >> 1;
 
	if ($list[$mid] == $x) {
		return $mid;
	} elseif ($list[$mid] > $x) {
		return binary_search($x, $list, $left, $mid-1);
	} elseif ($list[$mid] < $x) {
		return binary_search($x, $list, $mid+1, $right);
	}
}
 
echo binary_search($x, $list, 0, count($list)-1);

Итеративный бинарный поиск

$list = array(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144);
$x = 55;
 
function iterative_binary_search($x, $list) 
{
	$left = 0;
	$right = count($list)-1;
 
	while ($left <= $right) {
		$mid = ($left + $right) >> 1;
 
		if ($list[$mid] == $x) {
			return $mid;
		} elseif ($list[$mid] > $x) {
			$right = $mid - 1;
		} elseif ($list[$mid] < $x) {
			$left = $mid + 1;
		}
	}
 
	return -1;
}
 
echo iterative_binary_search($x, $list);

Осторожно: оптимизация

Большинство методов оптимизации, упомянутых в Интернете, рекомендуют заменить дорогостоящую операцию деления на 2 ее побитовым эквивалентом (n >> 1) == n / 2. Это не всегда верно, и это очень зависит от языка программирования. Таким образом, в PHP эти операции довольно похожи, так как PHP написан на C. Вы должны знать о специфических особенностях языка при оптимизации кода.

Фибоначчи Поиск

Каждый разработчик слышал о Фибоначчи и его последовательности. Алгоритм поиска Фибоначчи является практически разновидностью алгоритма двоичного поиска. На самом деле единственное отличие состоит в том, что алгоритм двоичного поиска делит список на две равные части, тогда как поиск Фибоначчи делит его на две, но не равные части. На самом деле иногда поиск выполняется быстрее, если разделить список на такие неравные подсписки. Однако длина подсписков не случайна.

Ясно, что отношение любых двух последовательных чисел в последовательности Фибоначчи практически формирует золотое сечение. Это может привести нас к другому варианту Фибоначчи и двоичному поиску — поиску золотого сечения. Разница лишь в том, что вы должны разделить длину списка на две части точно на золотое сечение.

Поиск Золотого Сечения

Поиск по золотому сечению не делит массив на два равных подсписка!

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

сложность

Сложность алгоритма двоичного поиска интуитивно понятна — O (log (n)), что делает его гораздо более эффективным, чем последовательный поиск.

журнал (п)

f (n) = log (n) по сравнению с f (n) = n

заявка

Бесполезно упоминать примеры его использования. Этот алгоритм прост в реализации и в то же время очень быстр. Да, действительно, этот алгоритм возможен только в отсортированных списках, и это ограничение. Кроме того, как я уже сказал, по сравнению с поиском прыжка здесь мы имеем более одного прыжка назад в большинстве случаев, что иногда может быть дороже, чем прыжок вперед. Однако это самый быстрый алгоритм поиска? Я постараюсь ответить на этот вопрос в моей следующей статье.

 

Источник: http://www.stoimen.com/blog/2011/12/26/computer-algorithms-binary-search/

33
Share: