Двоичный поиск - это типичный метод поиска, используемый в компьютерных науках на протяжении длительного времени. Это вычисление преследования, при котором сначала необходимо отсортировать все компоненты. В 1960 году Деррик Генри Леман распространил расчет параллельной охоты, который работал на всех экспонатах ПК.
Двоичный поиск следует стратегии Разделяй и властвуй, чтобы преодолеть недостаток алгоритма линейного поиска, который включает итерацию по всем элементам до тех пор, пока целевой элемент не будет найден. Двоичный поиск снизил линейный поиск на время его выполнения O (log2 n), которое меньше времени O (n). Здесь n - количество элементов в массиве.
Алгоритм
Здесь N - длина отсортированного массива, а k - элемент, который нужно найти.
low = 0
high = N-1
loop while low <= high
middle = low+(high-low)/2
if array[middle] == k
return middle
else if array[middle] < k
low = middle+1
else
high = middle-1
End loop
return Not Found
Из приведенного выше примера мы видим, что двоичный поиск намного лучше, чем линейный поиск.
В худшем случае для двоичного поиска требуются итерации log2 (n) +1, которые намного лучше, чем O (n).
Предположим, у нас есть 999 элементов в массиве размером 1000 чисел от 1 до 999. Нам нужно найти число 750. Для линейного поиска требуется 749 итераций, чтобы найти целевой элемент, в котором для двоичного поиска требуется только 2 итерации.
если итерация занимает 1 мс (миллисекунду), то линейный поиск занимает 749 мс, а двоичный поиск занимает всего 2 мс.
Анализ сложности
Сложность времени:
Сложность времени показывает, сколько времени потребовалось вашей программе для завершения процесса. Рассмотрим n - длину отсортированного массива.
Iteration 1: length of array = n. Iteration 2: length of array = n/2. Iteration 3: length of array = (n/2)/2. . . . Iteration k: length of array = (n/2)^k. After k divisions, the length of the array becomes 1. so, 1 = (n/2)^k. n = 2^k. Take base-2 Logarithm on both sides. log2 (n) = log2 (2^k). As per Logorithmic properties. log2(n) = k log2 (2). Therefore, log2 (n) = k [logA (A) = 1].
Выше мы успешно вычислили временную сложность алгоритма двоичного поиска.
Сложность пространства:
Space Complexity показывает, сколько памяти или других компьютерных ресурсов потребовалось вашей программой для завершения процесса.
Здесь для двоичного поиска требуется ноль лишнего места. Итак, пространственная сложность нашего алгоритма равна постоянное пространство O (1).
Время работы и использование кеша
При анализе производительности двоичного поиска еще одним соображением является время, необходимое для сравнения двух элементов. Для целых чисел и строк необходимое время увеличивается линейно по мере увеличения длины кодирования (обычно количества битов) элементов. Например, сравнение пары 64-битных целых чисел без знака потребует сравнения до удвоения битов по сравнению с парой 32-битных целых чисел без знака.
Худший случай достигается, когда целые числа равны. Это может быть значительным, когда длина кодирования элементов велика, например, с большими целочисленными типами или длинными строками, что делает сравнение элементов дорогостоящим. Кроме того, сравнение значений с плавающей запятой (наиболее распространенное цифровое представление действительных чисел) часто обходится дороже, чем сравнение целых чисел или коротких строк.
Повторяющиеся элементы
Предположим, наш массив содержит повторяющиеся копии целевого элемента k. В этом сценарии мы не можем сделать вывод, что наш алгоритм всегда возвращает первое вхождение целевого элемента. Он также может возвращать второе / последнее вхождение целевого элемента.
Итак, мы должны сказать, должен ли наш алгоритм возвращать первое или последнее вхождение целевого элемента.
Мы можем вернуть самое левое вхождение:
function binary_search_leftmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] < T:
L := m + 1
else:
R := m
return L
или крайнее правое вхождение:
function binary_search_rightmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] > T:
R := m
else:
L := m + 1
return R - 1
Здесь L = левый / низкий, R = правый / высокий, m = средний.
Рассмотрим этот пример: [4, 5, 5, 7, 8, 8, 8, 8, 9, 9]. Вам нужно найти диапазон целых 8, который вы должны вернуть в качестве вывода [4, 8]. Давайте спроектируем наш алгоритм. У нас может быть логическая переменная, чтобы сказать, ищем ли мы первое вхождение элемента или последнее.
Здесь, если наше логическое значение flag f истинно, мы собираемся найти первое вхождение нашего целевого элемента. Итак, рассматриваем левую часть массива. В противном случае мы рассматриваем правую часть массива, чтобы найти последнее вхождение нашего целевого элемента.
Приложения
Двоичный поиск имеет обширное применение при решении алгоритмических проблем, поскольку он имеет логарифмическое время выполнения. Это настоящий восторг программиста !.
Скажем, найти квадратный корень из целого числа. В нормальном программировании мы перебираем все элементы от 1 до N, чтобы найти квадратный корень. Некоторые умные программисты сокращают цикл наполовину N / 2. но в двоичном поиске
Реальные приложения:
отладка несколько линейного фрагмента кода. если в коде много шагов, которые в основном выполняются последовательно, и есть ошибка, вы можете изолировать ошибку, найдя самый ранний шаг, на котором код дает результаты, отличные от ожидаемых.
- выбор плохого изменения кода у релиз-кандидата. При продвижении большого выпуска кода в производство иногда обнаруживается проблема с этим двоичным кодом. Если откат всего выпуска был невозможен, разработчик релиза выполнял двоичный поиск по идентификаторам изменений кода. Он выяснил бы самое раннее изменение кода, которое создает ошибку.
- выяснение требований к ресурсам для большой системы. можно попробовать запустить нагрузочные тесты в системе и выполнить двоичный поиск минимального количества процессоров, необходимых для обработки прогнозируемой нагрузки. (этот подход лучше, чем случайное предположение, но намного хуже, чем некоторый анализ вашей системы и несколько хороших обоснованных предположений)
- выяснить, насколько большим должен быть размер вашего кеша для обслуживающей системы, или выбрать TTL для кеша.
Некоторые из проблем, которые можно решить только с помощью двоичного поиска:
1. Найдите такое число в массиве, где разрешены дубликаты.
2. Найдите количество экземпляров числа в массиве, если дублирование разрешено.
