Python Бинарный поиск - PullRequest
Новая
       13

Python Бинарный поиск

1 голос
/ 02 апреля 2020

Я начинающий программист, и я хотел создать свой собственный алгоритм двоичного поиска с нуля без какой-либо помощи. Можно с уверенностью сказать, что не все в порядке. Я надеялся, что кто-нибудь сможет найти ошибку в моем коде. Я исправил несколько проблем, но теперь столкнулся с проблемой, когда if не может найти значения, превышающие средний индекс, и он не заканчивается, когда достигает одного значения, не равного целевому значению. 

    import random

userInput = 100
numbers = []

for i in range(100):
    numbers.append(random.randint(0, 100))

#Adding 100 to use as a test
numbers.append(100)
numbers.sort()
print(numbers)

def binarySearch(list, target):
    midIndex = int(len(list)/2)
    midValue = list[midIndex]

    if midValue == target:
        print("We found " + str(target))

    elif target > midValue:
        newList = numbers[midIndex:]
        binarySearch(newList, target)

    elif target < midValue:
        newList = numbers[:midIndex]
        binarySearch(newList, target)

    elif len(list) == 1 and list[0] != target:
        print(target + " is not in the list")

    else:
        print("It's not in the list")

binarySearch(numbers, userInput)

1 Ответ

1 голос
/ 02 апреля 2020

У вашего кода есть две основные проблемы:

  1. mid используется для представления как индекса, так и значения.
  2. Конец binarySearch() никогда не бывает достигнут.

Проблема № 1: mid

При создании newList с использованием среза list вы используете mid в качестве индекса: 

elif target > mid:
    newList = numbers[mid:]

Однако mid не является индексом. Это значение в середине list: 

mid = list[int(len(list)/2)]

Попробуйте использовать две переменные: 

midIndex = int(len(list)/2)
midValue = list[midIndex]

Проблема № 2: binarySearch()

binarySearch() никогда не достигает финала elif, чтобы увидеть, что target отсутствует в списке.

Финал elif достигается только после проверки следующих условий: 

if midValue == target:
    ...
elif target > midValue:
    ...
elif target < midValue:
    ...

Ясно , если midValue и target - два числа, одно из этих сравнений должно возвращать True.

Из-за порядка выполненных проверок binarySearch() никогда не заканчивается тем, что попадает в этот раздел: 

elif len(list) == 1 and list[0] != target:
    ...

Чтобы решить эту проблему, попробуйте переставить операторы if так, чтобы binarySearch() достиг этой части кода.

...