遞歸在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

你的問題在於你在每個循環中重新聲明最小值和最大值，所以雖然它應該是遞歸的，但每次都會傳入新的最小值或最大值，這實際上並不是這樣。

您可以通過參數使用默認值解決這個問題：如果你不熟悉的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 

= MAX或LEN（名單）-1 最多會只有當max沒有傳遞給方法時，才設置爲len（list）-1。

因此，你可以簡單地使用調用的方法：

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 

順便說一下，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)