Блог

Главная - Вопросы по программированию - Реализовать подпрограмму двоичного поиска, но без результата

Реализовать подпрограмму двоичного поиска, но без результата

#python #function #search #indexing

#python #функция #Поиск #индексирование

Вопрос:

Детали алгоритма:

Учитывая массив A из n элементов с отсортированными значениями A[0] ≤ A[1] ≤ ... ≤ A[n−1] и целевым значением x, следующая подпрограмма использует двоичный поиск для поиска индекса x в A.

Вот код, который я написал:

 def Binarysearch(A, x): 
    L = 0 
    R = len(A)-1 
    M = (L   R)//2 
    while L<=R: 
        if A[M] < x: 
            L = M 1 
        elif A[M] > x: 
            R = M-1 
        else: 
            return M 
    
    return None

ПРОБЛЕМА:
Написав следующие строки, я не получаю результата:

 list = [2,3,4,5,12,15,76]
Binarysearch(list, 3)

Я хотел бы понять, в чем проблема.
Я заметил, что если я заменю после условия else: return M с помощью print(M), я получу бесконечную последовательность из 1.

Комментарии:

1. Может быть, вы хотели использовать возвращаемое значение значения функции и распечатать его?

2. Знакомы ли вы с интерактивными онлайн-инструментами — например. http://www.pythontutor.com/ — если вы просматриваете свой код, легче увидеть, где что-то пошло не так.

3. В сторону: не называйте свои переменные list ; это приведет к запутанным проблемам при попытке использовать list встроенный.

Ответ №1:

Проблема в том, что эта строка:

 M = (L   R)//2

Должно быть внутри цикла. В противном случае M никогда не обновляется, и вы переходите в бесконечный цикл.

Ответ №2:

Как указывалось в предыдущем сообщении от @BrianMcCutchon, недостаток в коде и рабочем решении. У вас проблема. теперь вы хорошо понимаете проблему.

Я только что предложил same решение с более описательными именами переменных здесь для вашей справки.

 def binary_iterative(A, target):
    ''' 
    Return the index of the target, or None if not found.

    The array A is in sorted order, and assumed each num. is unique.
    ''' 

    left, right = 0, len(A) - 1

    while left <= right:

        middle_idx = (left   right) // 2
        middle_num = A[middle_idx]

        if middle_num == target:
            return middle_idx
        
        elif middle_num < target:
            left = middle_idx   1
            
        elif middle_num > target:
            right = middle_idx - 1
            
    return None



if __name__ == '__main__':
    nums = [1, 3, 4, 5, 6, 9, 10, 12, 17, 20, 22]
    target = 5
    print(binary_iterative(nums, target))