Рубрики
Без рубрики

Алгоритм бинарного поиска в Python

Узнайте об алгоритме бинарного поиска и о том, как его реализовать в программировании на Python.

Автор оригинала: Robin Andrews.

Алгоритм Бинарного поиска является фундаментальным в информатике. Это очень умный алгоритм, который значительно сокращает время, необходимое для поиска элементов в больших наборах данных, по сравнению с менее эффективными подходами.

Важно отметить , что для использования двоичного поиска ваши данные должны быть отсортированы . Некоторые люди путаются с алгоритмами сортировки и алгоритмами поиска, группируя их вместе в своем мышлении, но стоит потратить некоторое время, чтобы немного упорядочить свой “инструментарий алгоритмов” и убедиться, что поиск и сортировка имеют свой собственный раздел. Просто в качестве напоминания см. Эти списки для некоторых примеров каждого из них:

Алгоритмы поиска

  • Линейный поиск
  • Бинарный поиск

Алгоритмы сортировки

  • Сортировка пузырьков
  • Сортировка вставки
  • Сортировка слиянием
  • Быстрая сортировка

Как работает Алгоритм Бинарного поиска?

Эта статья посвящена бинарному поиску и тому, как его написать с помощью Python . Прежде чем писать его в коде или псевдокоде, вам нужно тщательно понять процесс, и это лучше всего сделать, выполнив множество примеров вручную на бумаге или на доске. Вы можете получить очень хорошую интуицию о том, как работает алгоритм, играя в игру в угадайку с другом.

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

Если вы сыграете в эту игру несколько раз, вы быстро обнаружите, что некоторые стратегии угадывания числа более эффективны, чем другие. Например, представьте, что исходное число 13 , и вы догадываетесь 50 . Вам говорят, что ваша догадка слишком высока. Гадание 49 следующий не был бы хорошим выбором. Чтобы оптимизировать ваши шансы угадать число за как можно меньшее количество попыток, лучшая стратегия состоит в том, чтобы угадать на полпути между известными верхней и нижней границами фактического значения. Итак, если вы знаете, что число находится между 1 и 64 , вы должны догадаться 32 . Если вам скажут, что это слишком высоко, вы должны догадаться 16 , и так далее. Каждый раз, когда вы сокращаете вдвое пространство поиска , это означает, что вы гарантированно достигнете ответа за относительно несколько шагов. То есть суть того, как работает бинарный поиск .

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

Если вы изучаете информатику для экзамена, вам может потребоваться написать псевдокод для алгоритма двоичного поиска. Ниже приведена версия, в которой используется синтаксис, совместимый с руководством по псевдокодированию для экзаменационной комиссии OCR в Великобритании. Лично я считаю этот шаг педагогически избыточным , как объяснено в моей статье под названием Нам нужно поговорить о псевдокоде , но я включаю его здесь, поскольку это может помочь некоторым из вас.

// Binary search algorithm Pseudocode (OCR)

haystack = [7, 7, 22, 37, 47, 55, 57, 57, 86, 91] // MUST be sorted
needle = int(input("Enter the number you are searching for: "))
length = haystack.length
lower_bound = 0
upper_bound = length - 1
found = False

while found == False and lower_bound <= upper_bound:
    mid_point = (lower_bound + upper_bound) DIV 2
    if haystack[mid_point] == needle:
        print("You number has been found.")
        found = True
    elif haystack[mid_point] < needle:
        lower_bound = mid_point + 1
    else:
        upper_bound = mid_point - 1
        endif
endwhile
if found == False:
    print("Your number is not in the list.")
endif

Алгоритм использует важную технику под названием разделяй и властвуй , как упоминалось в видео. На каждом этапе половина набора данных отбрасывается, и алгоритм применяется к оставшемуся меньшему набору данных до тех пор, пока не будет найден элемент поиска или не будет выполнено условие выхода.

Это условие выхода является ключевым для этого алгоритма, и понимание того, почему это так, является хорошим признаком того, что вы понимаете весь алгоритм. По сути, у нас есть высокий указатель и низкий указатель, и мы проверяем элемент в середине этих двух указателей, чтобы увидеть, является ли он нашим элементом поиска. Если это так, отлично, мы выходим, в противном случае мы перемещаем либо высокий, либо низкий указатель таким образом, чтобы “зажать” наше значение.

Двоичный поиск в Python

Как только вы написали и поняли псевдокод, пришло время написать алгоритм на реальном языке программирования, таком как Python. Вы всегда должны иметь в виду конкретный пример, чтобы проверить, что ваша программа ведет себя так, как ожидалось. Итак, определите список (я часто называю его стог сена ) и элемент поиска ( игла ) и посмотрите, сможете ли вы заставить свою программу найти иглу в стоге сена. И помните: список должен быть отсортирован в первую очередь!

Попробуйте сейчас, а когда закончите или застрянете и вам понадобится помощь, ознакомьтесь с моей версией ниже.

"""Basic binary search algorithm"""

haystack = [7, 7, 22, 37, 47, 55, 57, 57, 86, 91]
needle = int(input("Enter the number you are searching for: "))
length = len(haystack)
lower_bound = 0
upper_bound = length - 1
found = False

while found == False and lower_bound <= upper_bound:
    mid_point = (lower_bound + upper_bound) // 2
    if haystack[mid_point] == needle:
        print("You number has been found.")
        found = True
    elif haystack[mid_point] < needle:
        lower_bound = mid_point + 1
    else:
        upper_bound = mid_point - 1
if found == False:
    print("Your number is not in the list.")

Эта статья основана на сообщение в моем блоге Compucase . Вы можете подписаться на наш список рассылки здесь .

Читайте ещё по теме: