Джон Гуттаг Упражнение с пальцами Глава 10

Question

Этот код взят из введения Guttag в программирование.Упражнение для пальца для раздела 10.3:

def search(L, e):
    """Assumes L is a list, the elements of which are in
     ascending order.
     Returns True if e is in L and False otherwise"""

     def bSearch(L, e, low, high):
         #Decrements high - low
         if high == low:
             return L[low] == e
         mid = (low + high)//2
         if L[mid] == e:
             return True
         elif L[mid] > e:
             if low == mid: #nothing left to search
                 return False
              else:
                 return bSearch(L, e, low, mid - 1)
         else:
             return bSearch(L, e, mid + 1, high)

     if len(L) == 0:
         return False
     else:
         return bSearch(L, e, 0, len(L) - 1)

Я не оборачиваюсь рекурсией.Почему при рекурсивном вызове 2 ^nd вместо mid используется mid+1?

Answer 1

Это бинарный поиск, поэтому в каждой рекурсии вы разбиваете список пополам.Если вы дошли до того, что сделали рекурсивный вызов, вы уже проверили элемент на mid, и это не то, что вы ищете (если бы это было так, вы бы вернули true, ине нужно будет повторяться).Поэтому вы выбираете направление для поиска (половина списка для поиска) и выполняете поиск в этой половине рекурсивно.Однако, независимо от того, какую половину вы выберете, вы уже знаете, что элемент в индексе mid не тот, который вы ищете , поэтому вам больше не нужно проверять его, поэтомунеобходимо включить его в список, к которому вы возвращаетесь.