Алгоритм двоичного поиска - это алгоритм поиска, который работает для отсортированных коллекций (например, отсортированных массивов). На входе он принимает коллекцию, длину этой коллекции и элемент, который нужно найти, и выдает в качестве вывода индекс элемента в коллекции (если он существует).
Этот алгоритм настолько же эффективен, насколько прост в освоении благодаря своей простоте.
Этот алгоритм выполняет только O (log n) сравнений.
С другой стороны, он работает только для отсортированных коллекций, что ограничивает его использование в некоторых конкретных случаях.
Этот пост призван показать некоторые основные различия между этими тремя языками программирования. Сам алгоритм используется во многих приложениях, но в большинстве случаев нам не нужно реализовывать его с нуля, потому что каждая библиотека для работы со структурой данных, достойная уважения, реализует это.
Псевдокод
Псевдокод алгоритма следующий:
function BSA(A, n, T): L := 0 R := n − 1 while L <= R: m := floor((L + R) / 2) if A[m] < T: L := m + 1 else if A[m] > T: R := m - 1 else: return m return unsuccessful
Поясним этот псевдокод:
- Алгоритм принимает в качестве входных данных массив
A
, длину массиваn
и элемент для поискаT
; - Мы инициализируем две переменные:
L
to0
иR
ton-1
, а именно индекс первого и последнего элемента массиваA
; - Мы выполняем итерацию до тех пор, пока
L
не станет равным или большим, чемR
, то есть когда мы перебираем весь массив; - Мы инициализируем
m
, чтобы он был полом или(L+R)/2
, а именно индексом элемента в середине массива; - Затем мы сравниваем элемент по индексу
m
с желаемым элементомT
: - если
A[m]
меньше, чемT
, мы должны искатьT
в большей половине массива: в той, что находится в [m + 1, R]; - если
A[m]
больше, чемT
, мы должны искатьT
в нижней половине массива: в той, что находится в [L, m-1]; - в противном случае
A[m]
равноT
, и мы можем вернутьm
, потому что мы нашли элемент.
Python
Давайте посмотрим на BSA с использованием Python.
Как видите, BSA, написанный на Python, очень похож на псевдокод. Мы возвращаем -1, когда не можем найти нужный элемент.
Go
Версия Go BSA следующая:
В отличие от версии Python, этот код не похож на псевдокод из-за строгой типизации Go, которая заставляет нас выполнять 2 преобразования (строка 7). Также в реализации Go мы возвращаем -1, если не можем найти элемент T. Из-за простоты самого алгоритма никаких других соображений не требуется.
C
Версия C _BSA_ может быть следующей:
Реализация C очень похожа на реализацию Go, но не имеет приведений, поскольку C имеет слабую типизацию.
Это мой первый пост в блоге.