Отладка бинарного поиска - PullRequest
Новая
       11

Отладка бинарного поиска

2 голосов
/ 13 марта 2019

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

def binary_search(array, value, low, high):
    if high < low:
        return -1
    else:
        mid = (low + high)/2;
        if array[mid] > value:
            return binary_search(array, value, low, mid)
        elif array[mid] < value:
            return binary_search(array, value, mid+1, high)
        else:
            return mid
array = []
for i in xrange(10000):
    array.append(input())
for i in xrange(10000):
    value = input()
    answer = binary_search(array, value, 0, 9999)
    print("%d" % answer)

Ввод:

Ввод состоит из отсортированного массива длиной 10 000, за которым следуют 10 000 запросов.Каждое целое число задается в отдельной строке (всего их 20 000).

Гарантируется, что в массиве нет дубликатов.

Вывод:

ДляДля каждого значения запроса выведите одну строку вывода, содержащую одно целое число: индекс, соответствующий значению запроса, или -1, если значение отсутствует в массиве.

Я пытался исправитьэтот код в течение нескольких дней ... Я вполне уверен, что параметры для рекурсии внутри, если предложение неправильно.Не должно ли это быть: 

if array[mid] > value:
            return binary_search(array, value, low, mid-1)

Потому что в противном случае, если в массиве только один элемент и элемент> value, он будет бесконечно зацикливаться.Но полученный код все еще помечен как неправильный ответ согласно оценщику!

Другие подозреваемые:

  1. ';'в mid = (low + high)/2; Несмотря на резкое колебание, он все равно прекрасно компилируется
  2. (low + high)/2 Поскольку это написано в Python 2.7, это эквивалентно (low + high)//2 в Python 3, верно?Так что никаких проблем здесь ...

Любая помощь приветствуется.Спасибо.

1 Ответ

0 голосов
/ 13 марта 2019

Ошибка чуть дальше! 

if high < low: #ERROR IS HERE
    return -1

Это приведет к бесконечной рекурсии, если value не в array.

Рассуждение:

Значение high будет никогда не будет ниже значения low. Это связано с тем, что эти значения изменяются только путем замены их на mid в рекурсивном вызове. Начиная с mid=(high+low)//2, в конечном итоге они будут оба 0 или high. А начиная с (0+0)//2 == 0 и (high+high)//2 == high вы в конечном итоге будете выполнять бесконечную рекурсию до тех пор, пока стек не взорвется. Таким образом, ваше исправление выглядит просто if high <= low:.

Теперь возникает новая проблема:

Что если мы посмотрим на значение high или 0? Тогда мы получим -1, потому что значения одинаковы. Решение, уточните утверждение if:

if high <= low and array[(low+high)//2] != value:

Этот код гарантирует, что если первое условие выполнено, мы также гарантируем, что средний элемент на самом деле не является искомым значением.

...