Рекурсивный поиск пополам, чтобы получить индекс цели - PullRequest
Новая
       24

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

1 голос
/ 20 марта 2019

Я попытался выполнить поиск по индексу находки с помощью алгоритмов деления пополам 

def bi_search(nums: List[int], find: int) -> int:
    """
    Return the index of the find 
    """
    if len(nums) == 0:
        return -1
    else:
        mid = len(nums) // 2  #testEntry
        if find == nums[mid]:
            return mid 
        if find < nums[mid]:
            sub_nums = nums[:mid]
            return bi_search(sub_nums, find)  

        if find > nums[mid]:
            sub_nums = nums[mid:]
            return bi_search(sub_nums, find) #recursive case.

, но он не работает должным образом 

In [26]: bi_search(list(range(1000)), 777)                     
Out[26]: 4

Возвращает середину базового случая.

Я заметил, что правильный индекс можно получить, используя методы итерации, как в bisect - Алгоритм деления массива - Документация Python 3.7.3rc1

Возможно ли получить правильный индексв рекурсивном решении?

1 Ответ

1 голос
/ 20 марта 2019

Если добавить в функцию оператор print() и использовать меньший пример, вы увидите проблему: 

def bi_search(nums, find):
    print((nums, find))
    ...

print(bi_search(list(range(10)), 7))

Вывод: 

([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 7)   # Looks good.
([5, 6, 7, 8, 9], 7)                  # Also good.
2                                     # Doh!

Проблема в том, чтоВы возвращаете индекс в последний проверенный список , а не индекс начальный список .Чтобы ваш подход работал, вам нужно передавать больше информации через рекурсивные вызовы - и это становится сложнее.

Другой подход состоит в том, чтобы передавать полный список для каждого вызова и вместо этого корректировать нижнюю / верхнюю границыдля поиска, как вы идете.Это также позволяет избежать создания новых списков при каждом вызове.Например: 

def bi_search(nums, find, i = None, j = None):
    # Setup.
    N = len(nums)
    if i is None:
        i = 0
        j = N - 1
    # Base case for failure.
    if j < i:
        return None
    # Success or recurse.
    mid = (i + j) // 2
    if find == nums[mid]:
        return mid 
    elif find < nums[mid]:
        return bi_search(nums, find, i, mid - 1)
    else:
        return bi_search(nums, find, mid + 1, j)
...