Алгоритм двоичного поиска - это алгоритм поиска, который работает для отсортированных коллекций (например, отсортированных массивов). На входе он принимает коллекцию, длину этой коллекции и элемент, который нужно найти, и выдает в качестве вывода индекс элемента в коллекции (если он существует).

Этот алгоритм настолько же эффективен, насколько прост в освоении благодаря своей простоте.

Этот алгоритм выполняет только 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;
  • Мы инициализируем две переменные: Lto 0 и Rto n-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 имеет слабую типизацию.

Это мой первый пост в блоге.