Поиск в двоичном массиве – Python

Здравствуйте, я научу вас, как выполнить простой бинарный поиск в 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. (Найти число или нет)

Оцените статью
Procodings.ru
Добавить комментарий