Бинарный или двоичный поиск в Python

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

По своей сути алгоритм двоичного поиска в Python выполняет следующие шаги:

  1. Сравните целевое значение со средним элементом списка.
  2. Если они не равны, исключается та половина, в которой невозможно найти цель.
  3. Повторяйте эти шаги до тех пор, пока целевое значение не будет найдено или пока оставшийся список не станет пустым.

Этот процесс исключения делает алгоритм двоичного поиска очень эффективным. Его временная сложность составляет O(log n), где n — число элементов в списке.

Давайте реализуем алгоритм двоичного поиска на языке Python. Мы создадим функцию, которая будет принимать на вход отсортированный список и целевое значение. Функция должна возвращать индекс целевого значения в списке. Если целевого значения нет в списке, функция должна вернуть -1.

Вот код Python для двоичного поиска:

def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low  target:
            high = mid - 1
        else:
            low = mid + 1
    return -1

# test the function
print(binary_search([1, 2, 3, 4, 5], 3))

В этой функции Python сначала мы создаём два указателя — нижний и верхний — и устанавливаем их на первый и последний индексы списка соответственно. Затем мы запускаем цикл while, который будет выполняться до тех пор, пока значение нижнего указателя меньше или равно значению верхнего.

На каждой итерации Python мы вычисляем индекс среднего элемента(mid) и самого среднего элемента:

  • Если догадка равна цели, мы нашли цель и возвращаемся в середину.
  • Если предположение больше целевого значения, мы знаем, что цель должна находиться в левой половине списка, поэтому мы регулируем высокое значение до среднего — 1. Если предположение меньше целевого значения, мы регулируем низкое значение до среднего + 1.

Если цикл Python while завершается и не находит цель, то мы возвращаем -1, чтобы показать, что цели нет в списке.

Выход:

Программа для двоичного поиска

Пример

Давайте рассмотрим пример. У нас есть список городов США, отсортированный по численности населения. Наша задача — определить позицию конкретного города в этом списке.

Представьте, что у нас есть список десяти самых густонаселенных городов США:

cities = ["New York", "Los Angeles", "Chicago", "Houston", "Phoenix", "Philadelphia", "San Antonio", "San Diego", "Dallas", "San Jose"]

Чтобы использовать алгоритм двоичного поиска в Python для определения местоположения города в списке, нам нужно преобразовать названия городов в числовые значения. Например, мы можем присвоить каждому городу индекс в алфавитном списке всех городов США.

Для этого примера допустим, что мы присвоили городам следующие числовые идентификаторы:

city_ids = [5, 4, 1, 2, 8, 7, 9, 6, 3, 10]

Теперь список отсортирован:

sorted_city_ids = sorted(city_ids)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Теперь предположим, что мы хотим найти позицию Сан-Диего (с идентификатором 6) в этом списке. Вот как мы могли бы использовать алгоритм двоичного поиска в Python:

def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low  target:
            high = mid - 1
        else:
            low = mid + 1
    return -1

# test the function
print(binary_search(sorted_city_ids, 6))

В этом случае функция Python binary_search возвращает значение 5. Это означает, что Сан-Диего — шестой по численности населения город в отсортированном списке городов США.

Выход:

Пример двоичного поиска в Python

Заключение

Бинарный поиск — это высокоэффективный алгоритм поиска с временной сложностью O(log n). Эта эффективность достигается за счет сокращения вдвое пространства поиска на каждой итерации, что резко сокращает количество необходимых сравнений. Код Python для двоичного поиска прост и элегантен, демонстрируя силу алгоритмического мышления.

Добавить комментарий