Алгоритм поиска — это алгоритм, который ищет данные в наборе данных. Двумя распространенными примерами алгоритмов поиска являются линейный и бинарный поиск. Здесь мы узнаем, как реализовать поиск в списке целых чисел, используя оба алгоритма поиска. Мы начнем с концептуального обзора шагов алгоритма, а затем закодируем решение на Python.
Во-первых, что такое линейный поиск и что такое бинарный поиск и чем они отличаются? Когда вы предпочитаете один вид поиска другому? И чем эти алгоритмы отличаются по временной и пространственной сложности? Сначала ответим на эти вопросы.
Линейный поиск
Линейный поиск — это алгоритм поиска, который начинается с начала списка и проверяет каждый элемент, пока не будет найден ключ поиска или не будет достигнут конец списка. Линейный поиск будет сравнивать все элементы, если ключ поиска отсутствует.
Сложность времени линейного поиска
Если каждое сравнение занимает 1 мкс (1 микросекунду), время выполнения алгоритма линейного поиска составляет до 1 с для поиска в списке с 1 000 000 элементов, 10 с для 10 000 000 элементов и так далее. Пример: поиск в интернет-магазине Amazon, в котором представлено более 200 миллионов товаров, может занять более 3 минут. Этот алгоритм обычно использует количество шагов, пропорциональное размеру входных данных.
Для списка с 32 элементами линейный поиск требует не более 32 сравнений: 1 сравнение, если ключ поиска найден по индексу 0, 2, если найден по индексу 1, и так далее, до 32 сравнений, если ключ поиска не найден. Таким образом, для списка с N элементами линейный поиск требует не более N сравнений.
Линейный поиск и бинарный поиск
Линейный поиск может потребовать поиска всех элементов списка, что может привести к увеличению времени выполнения. Допустим, мы хотим найти контакт на смартфоне. Поиск по одному от первого до последнего может занять много времени. Поскольку список контактов сортируется, более быстрый поиск, известный как двоичный поиск, сначала проверяет средний контакт. Если нужный контакт находится в алфавитном порядке перед средним контактом, бинарный поиск будет искать первую половину, а в противном случае - последнюю половину. Каждый шаг уменьшает количество контактов, которые необходимо найти, наполовину.
Двоичный поиск — это более быстрый алгоритм поиска в списке при двух условиях: (1) если элементы списка отсортированы и (2) они доступны напрямую (например, в массиве).
Временная сложность бинарного поиска
Двоичный поиск очень эффективен при поиске элемента в отсортированном списке. Во время каждой итерации алгоритма бинарный поиск уменьшает пространство поиска (т. е. оставшиеся элементы для поиска) наполовину. Поиск завершается, когда элемент найден или область поиска пуста (элемент не найден).
Например, для списка из 32 элементов, если ключ поиска не найден, пространство поиска делится пополам и содержит 16 элементов, затем 8, 4, 2, 1 и, наконец, ни одного, что требует всего 6 шагов.
Давайте теперь вернемся к нашему примеру с Amazon. Для поиска в интернет-магазине Amazon, в котором представлено более 200 миллионов товаров, требуется менее 28 мкс; до 7 000 000 раз быстрее, чем линейный поиск. 3 минуты в случае использования линейного поиска против 28 микросекунд при использовании бинарного поиска. Конечно, я должен отметить, что сравнение реального времени в минутах/микросекундах — не лучший подход, когда речь идет об анализе сложности. Мы хотим использовать объективное измерение того, сколько времени требуется для запуска обоих алгоритмов, и мы хотим, чтобы они не зависели от аппаратного обеспечения. В этом примере все, что я пытаюсь указать, — это существенная разница между производительностью алгоритмов линейного и бинарного поиска.
Алгоритм бинарного поиска также находит расположение значения ключа в списке, но намного быстрее, чем линейный поиск, поскольку поиск выполняется в отсортированном списке. Двоичный поиск сравнивает средний элемент списка с ключом. Если средний элемент соответствует ключу, то алгоритм завершен и возвращает индекс. Если ключ меньше среднего элемента, цикл продолжает поиск в первой половине списка. Если ключ больше среднего элемента, цикл продолжает поиск в последней половине списка. Таким образом, поле поиска всегда сокращается вдвое, что приводит к гораздо меньшему количеству сравнений.
Чтобы вычислить индекс в середине левого и правого указателей, сумма правого и левого указателей делится на 2. Если результат не является целым числом, значение округляется до целого числа с использованием деления пола. В Python есть специальный оператор деления пола //, который автоматически отбрасывает десятичную часть частного, поэтому этот оператор используется при вычислении среднего индекса указателя: middle = (left + right) // 2.
Шаги алгоритма бинарного поиска
Давайте разберем алгоритм бинарного поиска шаг за шагом:
Список отсортированных идентификаторов пользователей:
user_ids = [4, 6, 10, 13, 18, 22, 30, 35, 50, 67]
L M R
Ключ, который мы ищем: target=50
левый_указатель индекс = 0
индекс правого указателя = 9
mid_pointer = левый указатель + правый указатель // 2 = индекс 4.5 округляется до 4 в меньшую сторону
Мы сравниваем наше целевое число со значением mid_pointer
Mid_pointer = цель? #Нет
Является ли mid_pointer ‹ целью? #Нет
Является ли mid_pointer › целью? #Да
Мы перемещаем указатель right_pointer в позицию mid_pointer — 1, тем самым уменьшая размер области поиска.
Далее мы пересчитываем позицию mid_pointer
mid_pointer левый указатель(0) + правый указатель(3) // 2 = индекс 1.5 округляется до 1 в меньшую сторону
Теперь наши указатели выглядят так:
user_ids = [4, 6, 10, 13, 18, 22, 30, 35, 50, 67]
L M R
Mid_pointer = цель? #Нет
mid_pointer ‹ target, поэтому каждый элемент перед mid_pointer также меньше target, так как мы имеем дело с отсортированным массивом
Перемещаем указатель left_pointer на одну позицию вправо от указателя mid_pointer (mid_pointer + 1)
Мы стираем mid_pointer и теперь у нас осталось:
user_ids = [4, 6, 10, 13, 18, 22, 30, 35, 50, 67]
L R
Снова пересчитываем позицию mid_pointer:
mid_pointer левый указатель(2) + правый указатель(3) // 2 = индекс 2.5 округляется до 2 в меньшую сторону
Mid_pointer = цель? #Нет
Перемещаем указатель left_pointer на одну позицию вправо от указателя mid_pointer (mid_pointer + 1)
user_ids = [4, 6, 10, 13, 18, 22, 30, 35, 50, 67]
LR
Снова пересчитываем позицию mid_pointer:
mid_pointer левый указатель(3) + правый указатель(3) // 2 = индекс 3
Mid_pointer = цель? Да! Теперь мы закончили и возвращаем искомое значение индекса.
Временная сложность этого алгоритма равна O(log n), потому что мы исключаем половину элементов в каждой точке.
Рекурсивная реализация бинарного поиска
O (журнал (n)) время | O(log(n)) пробел (поскольку мы добавляем кадры в стек вызовов с помощью рекурсии)
user_ids = [4, 6, 10, 13, 18, 22, 30, 35, 50, 67]
target = 50
def binary_search(array, target):
return binary_search_helper(array, target, 0, len(array) -1)
def binary_search_helper(array, target, left, right):
#base case
if left > right:
return -1
middle = (left + right) // 2
mid_val = array[middle]
if target == mid_val:
return middle
elif target < mid_val:
return binary_search_helper(array, target, left, middle - 1)
else:
return binary_search_helper(array, target, middle + 1, right)
binary_search(user_ids, target)
Подробнее о рекурсии здесь.
Итеративное внедрение бинарного поиска
O (журнал (n)) время | O(1) пробел
def binary_search(array, target, left, right):
while left <= right:
middle = (left + right) // 2
mid_val = array[middle]
if target == mid_val:
return middle
elif target < mid_val:
right = middle - 1
else:
left = middle + 1
return -1
binary_search(user_ids, target, 0, len(user_ids) - 1)
Когда использовать линейный поиск
Временная сложность линейного поиска составляет O(n). В худшем случае, в списке из 20 элементов, ваш алгоритм выполнит 20 шагов. В лучшем случае это O(1), потому что элемент, который вы ищете, может быть первым элементом. Рассмотрите возможность использования линейного поиска, когда ваши данные не отсортированы. Если ваши данные отсортированы, вы можете использовать более эффективный бинарный поиск. Когда вы программируете в реальном мире, вместо написания собственного линейного поиска вы можете использовать встроенное в Python ключевое слово in. Пример: print(18 в user_id) #True
Когда использовать бинарный поиск
Бинарный поиск занимает время O(log(n)). Как мы теперь знаем, он более эффективен, чем алгоритм линейного поиска, потому что вам не нужно искать по всему списку. Эффективность бинарного поиска имеет огромное значение, когда вы имеете дело с большим объемом данных, например. список миллионов чисел. Если вы выполнили линейный поиск, вам может потребоваться миллион шагов, чтобы завершить поиск. Логарифмический бинарный поиск занял бы всего 20 шагов. Чтобы написать бинарный поиск на Python, вы можете использовать встроенный инструмент, такой как bisect_left из модуля bisect, который находит индекс существующего элемента в отсортированном списке, используя бинарный поиск.
