Рекурсия бинарный поиск в Python

Question

У меня есть список с номерами 0-9:

mylist = list(range(10)) 

Я получаю сообщение об ошибке с помощью команды деления, чтобы получить mid:

def binary_search(mylist, element, low, high): 
    low=0 
    high= len(mylist) 
    mid=low + (high- mymin)/2 
    if mid==len(mylist): 
     return False 
    elif mylist[mid]==element: 
     return mid 
    elif high==low: 
     return False 
    elif mylist[mid]<element: 
     return binary_search(mylist, element, mymin, mid-1) 
    elif mylist[mid]<element: 
     return binary_search(mylist, element, mid+1, mymax) 
    else: 
     return mid 

и если бы я хотел вернуть True, как бы я написал, что поверх return binary_search(mylist, element, mymin, mid-1)?

Answer 1

Ваш первый даже не начнется, потому что list(mid) немедленно поднимет TypeError: 'list' object is not callable.

Если исправить (с помощью list[mid]), следующая проблема состоит в том, что вы игнорируете min и max аргументы, которые вы получаете, и вместо того, чтобы установить их 0 и len(list)-1 каждый раз. Таким образом, вы будете бесконечно возвращаться (до тех пор, пока вы не получите RecursionError для достижения предела стека).

Подумайте об этом: первый звонок binarySearch(l, 5, 0, 10) рекурсивно вызывает binarySearch(l, 5, 0, 4). Но этот вызов игнорирует это 4 и действует так, как будто вы прошли 10, поэтому он рекурсивно вызывает binarySearch(l, 5, 0, 4). Какой звонит binarySearch(l, 5, 0, 4). И так далее.

Если вы исправите это (удалив эти две строки), у вас возникла еще одна проблема. Когда вы даете ему номер 10, binarySearch(l, 10, 0, 10) позвонит binarySearch( л, 10, 6, 10) , which will call BinarySearch (l, 10, 8, 10), то binarySearch( л, 10, 9, 10) , then BinarySearch (l, 10, 10, 10). И последний будет проверять list[10] > element. Но list[10] собирается поднять IndexError, потому что в нем нет 11 элементов.

И как только вы исправите эту ошибку, проблемы не остались. Проблема, о которой вы просили, не может произойти. Вот пример:

>>> a = range(10) 
>>> for i in -3, -1, 0, 1, 4, 5, 9, 10, 11: 
...  print i, binarySearch(a, i, 0, 10) 
-3 False 
-1 False 
0 0 
1 1 
4 4 
5 5 
9 9 
10 False 
11 False 

---

Ваша вторая версия не является рекурсивной. bSearch никогда не вызывает bSearch, и это все определение рекурсии.

Нет ничего плохого в написании итеративного алгоритма вместо рекурсивного алгоритма (если вы не выполняете домашнюю проблему, а рекурсия - это целая точка), но ваша функция также не является итеративной: никаких петель нет.

(Эта версия также игнорирует start и end аргументов, но это не так много проблем в этом случае, потому что, опять же, вы не делаете никакой рекурсии.)

Во всяком случае, только return False в функция находится в этом первом if len(list) == 0. Таким образом, для любого непустого списка он либо собирается вернуть True, либо номер. С вашим вводом он вернет 4 для чего-либо меньшего, чем значение в середине списка (5), и True для чего-нибудь еще.

Answer 2

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

Вы можете решить эту проблему с помощью значений по умолчанию в аргументах:

def binary_search(list, element, min=0, max=None): 
    max = max or len(list)-1 

    if max<min: 
     return False 
    else: 
     mid= min + (max-min)/2 

    if mid>element: 
     return binary_search(list, element, min, mid-1) 
    elif mid<element: 
     return binary_search(list, element, mid+1, max) 
    else: 
     return mid 

Если вы не знакомы с синтаксисом на линии 2, макс = тах или Len (список) -1 макс будет set to len (list) -1, только если max не передается методу.

Таким образом, вы можете вызвать метод просто с помощью:

binary_search(range(10), 7) 
# Returns 7 

binary_search(range(10), 11) 
# Returns False 

Answer 3

Первое решение выглядит неправильно, потому что не индексирует список.

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

Вот что я закончил с:

def binary_search(value, items, low=0, high=None): 
    """ 
    Binary search function. 
    Assumes 'items' is a sorted list. 
    The search range is [low, high) 
    """ 

    high = len(items) if high is None else high 
    pos = low + (high - low)/len(items) 

    if pos == len(items): 
     return False 
    elif items[pos] == value: 
     return pos 
    elif high == low: 
     return False 
    elif items[pos] < value: 
     return binary_search(value, items, pos + 1, high) 
    else: 
     assert items[pos] > value 
     return binary_search(value, items, low, pos) 

И когда я проверить это, ответы выглядеть правильно:

In [9]: for val in range(7): 
    ...:  print val, binary_search(val, [1, 2, 3, 5]) 
    ...: 
0 False 
1 0 
2 1 
3 2 
4 False 
5 3 
6 False 

Btw, Python имеет модуль библиотеки для всего такого рода вещи по имени bisect.

Answer 4

Просто еще один ответ на тот же вопрос:

def binary_search(array, element, mini=0, maxi=None): 
    """recursive binary search.""" 

    maxi = len(array) - 1 if maxi is None else maxi 

    if mini == maxi: 
    return array[mini] == element 
    else: 
    median = (maxi + mini)/2 
    if array[median] == element: 
     return True 
    elif array[median] > element: 
     return binary_search(array, element, mini, median) 
    else: 
     return binary_search(array, element, median+1, maxi) 

print binary_search([1,2,3],2) 

Answer 5

Вы можете использовать список нарезку тоже.

def binary_search_recursive(list1, element): 
    if len(list1) == 0: 
     return False 
    else: 
     mid = len(list1)//2 
     if (element == list1[mid]): 
      return True 
     else: 
      if element > list1[mid]: 
       return binary_search_recursive(list1[mid+1:],element) 
      else: 
       return binary_search_recursive(list1[:mid],element) 

Однако обратите внимание, что нарезка списка вводит дополнительную сложность.

Answer 6

Здесь уже много решений, ниже представлено еще одно решение без нарезки и просто требуется элемент и список в качестве аргументов.

def binary_search(item, arr): 
    def _binary_search(item, first, last, arr): 
     if last < first: 
      return False 
     if last == first: 
      return arr[last] == item 
     mid = (first + last) // 2 
     if arr[mid] > item: 
      last = mid 
      return _binary_search(item, first, last, arr) 
     elif arr[mid] < item: 
      first = mid + 1 
      return _binary_search(item, first, last, arr) 
     else: 
      return arr[mid] == item 

    return _binary_search(item, 0, len(arr) - 1, arr) 
print(binary_search(-1, [0, 1, 2, 3, 4, 5]))``` 

Answer 7

Рекурсивный решение:

def binary_search_recursive(arr, elem, start=0, end=None): 
    if end is None: 
     end = len(arr) - 1 
    if start > end: 
     return False 

    mid = (start + end) // 2 
    if elem == arr[mid]: 
     return mid 
    if elem < arr[mid]: 
     return binary_search_recursive(arr, elem, start, mid-1) 
    # elem > arr[mid] 
    return binary_search_recursive(arr, elem, mid+1, end) 

Итерационный решение:

def binary_search_iterative(arr, elem): 
    start, end = 0, (len(arr) - 1) 
    while start <= end: 
     mid = (start + end) // 2 
     if elem == arr[mid]: 
      return mid 
     if elem < arr[mid]: 
      end = mid - 1 
     else: # elem > arr[mid] 
      start = mid + 1 

    return False 

Answer 8

Я сделал это. Исправьте меня, если есть какая-то ошибка.

import math 

def insert_rec(A,v,fi,li): 

    mi = int(math.floor((li+fi)/2)) 

    if A[mi] == v: 
     print("Yes found at: ",mi) 
     return 

    if fi==li or fi>li: 
     print("Not found") 
     return 

    if A[mi] < v: 
     fi = mi+1 
     insert_rec(A,v,fi,li) 

    if A[mi] > v: 
     li = mi-1 
     insert_rec(A,v,fi,li)