Здравствуйте, я научу вас, как выполнить простой бинарный поиск в python.
Для начала необходимо знать, что такое бинарный поиск. Двоичный поиск в основном заключается в делении массива на 2 несколько раз, пока не будет найдено искомое число.
Давайте перейдем непосредственно к коду, и вы поймете все по ходу объяснения:
В массиве у нас есть первый индекс и последний индекс, например:
lista = [2, 4, 6, 8, 10]
Помните, что список, по которому будет производиться поиск, должен быть упорядочен
Наш первый индекс равен 0, в этом случае list[0] = 2
Наш последний индекс равен 4, в этом случае list[4] = 10
С учетом этого, давайте продолжим:
low = 0
high = len(lista) - 1
Метод len возвращает количество элементов в списке, в данном случае 5. Но мы не хотим этого, мы хотим, чтобы high был последним индексом нашего списка, поэтому мы ставим -1 в конце
Теперь нам нужен цикл, чтобы пройтись по нашему списку, давайте воспользуемся циклом while.
while(high >= low):
middle = (high + low) // 2
if z == lst[middle]:
return print('achou')
else:
if z < lst[middle]:
high = middle - 1
else:
low = middle + 1
Давайте, я буду объяснять этот цикл построчно.
Условие, которое мы передаем в цикле while, следующее: Пока наш наибольший индекс больше нашего наименьшего индекса, запускайте программу:
Если это условие истинно, мы получаем половину массива (списка), который мы объявили в начале этого объяснения.
Половина массива получит сумму двух индексов (старшего и младшего), деленную на 2, скажем, что старший индекс равен 4, мы будем иметь как половину
2.
middle = (high + low) // 2
Это прекрасно. Теперь перейдем к проверкам.
Если найденное число (в данном случае это параметр ‘z’) равно половине нашего списка (list[middle], что в данном случае равно 2), то мы возвращаем что-то, показывающее, что мы нашли найденное число, и заканчиваем работу с программой.
if z == lst[middle]:
return print('achou')
Если искомое число отличается от половины списка, мы проверяем, больше или меньше половины списка искомое число.
Если z (искомое число) < list[middle] (half), то мы знаем, что z находится между первым числом (low) и половиной (middle), поэтому мы знаем, что нам не нужно больше никаких чисел справа от половины, и нет причин искать число там, где его не может быть.
Если эта проверка верна, то отныне последнее число - это новая половина - 1 (Почему -1? Потому что мы знаем, что наше число меньше половины, поэтому оно никогда не может быть половиной, но может быть на одно число меньше половины)
if z < lst[middle]:
high = middle - 1
Теперь, если это условие ложно, нам остается проверить еще одно условие, которым будет z > list[middle], поскольку мы уже проверили, является ли z == половиной или z < половиной.
Если z > половина, мы будем игнорировать все, что меньше половины, так как z не может быть там. Так что же нам делать? Нашим первым числом будет новая половина + 1 (Опять же, почему +1? Потому что мы знаем, что z не равно половине, но может быть половиной + 1)
else:
low = middle + 1
После этого он будет делать это столько раз, сколько необходимо, пока условие while не вернет false. (Найти число или нет)