python - 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)？

score 10 · Accepted Answer

递归解决方案：

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

score 7 · Accepted Answer

如果您是以下情况，这是一个优雅的递归解决方案：

1)在减半之前，尝试在传入的原始列表中返回目标的 INDEX 。获得目标是容易的部分。

2) 只需要传入2 个参数：(list, target) 而不是 4 个参数，包括递归传入的每个数组的上/下（右/左）边界。

3) 不希望越界、最大递归深度或未找到目标错误。

# Base Case: one item (target) in array.
# Recursive Case: cut array by half each recursive call.


def recursive_binary_search(arr, target):
    mid = len(arr) // 2
    if len(arr) == 1:
        return mid if arr[mid] == target else None
    elif arr[mid] == target:
        return mid
    else:
        if arr[mid] < target:
            callback_response = recursive_binary_search((arr[mid:]), target)
            return mid + callback_response if callback_response is not None else None
        else:
            return recursive_binary_search((arr[:mid]), target)

score 2 · Accepted Answer

第一个解决方案看起来不对，因为它没有索引列表。

当我第一次编写解决方案时，这个问题也让我感到困惑，所以一定要很好地测试你的算法。

这就是我最终得到的结果：

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的东西。

score 2 · Accepted Answer

`如果我错了，请纠正我，因为我是一名新程序员，但这是我的解决方案：

def binary_search(test_cases, item_to_be_found):
    try:
        if item_to_be_found == test_cases[len(test_cases) // 2]:
            return True
        elif item_to_be_found < test_cases[len(test_cases) // 2]:
            test_cases = test_cases[:len(test_cases) // 2]
        else:
            test_cases = test_cases[len(test_cases) // 2:]
        return binary_search(test_cases, item_to_be_found)
    except RecursionError:
        return False

score 1 · Accepted Answer

这里已经有很多解决方案了。下面是另一种没有切片的解决方案，只需要元素和列表作为参数：

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]))

score 1 · Accepted Answer

您也可以使用列表切片。

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)

但是，请注意，列表切片会带来额外的复杂性。

score 1 · Accepted Answer

请纠正我，如果代码出现任何错误

def binary_recursive(array, val):
    if val < array[0] or val > array[-1]:
        return False
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]
    if val == array[mid]:
        return True
    elif array[mid] > val:
        return binary_recursive(left, val)
    elif array[mid] < val:
        return binary_recursive(right, val)
    else:
        return False

score 1 · Accepted Answer

虽然为时已晚，但它可能会帮助其他人:-

def bsearch_helper(arr, key, low, high):
    if low > high:
        return False
    mid = (low + high)//2
    if arr[mid] == key:
        return True
    elif arr[mid] < key:
        return bsearch_helper(arr, key, mid + 1, high)
    else:
        return bsearch_helper(arr, key, low, mid - 1)
    return False

def bsearch(arr, key):
    return bsearch_helper(arr, key, 0, len(arr) - 1)

if __name__ == '__main__':
    arr = [8, 3, 9, 2, 6, 5, 1, 7, 4]
    print (bsearch(sorted(arr), 5))

score 0 · Accepted Answer

你的问题是你在每个循环中重新声明 min 和 max，所以虽然它应该是递归的，每次都传入一个新的 min 或 max，但这实际上并没有发生。

您可以通过在参数中使用默认值来解决此问题：

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 行的语法，只有在未将 max 传递给方法时，max = max 或 len(list)-1 max 才会设置为 len(list)-1。

因此，您可以简单地使用以下方法调用该方法：

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

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

score 0 · Accepted Answer

同一个问题的另一个答案：

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)

score 0 · Accepted Answer

你的第一个甚至不会开始，因为list(mid)会立即引发TypeError: 'list' object is not callable.

如果你修复它（通过使用list[mid]），你的下一个问题是你忽略你收到的minandmax参数，而是将它们设置为0andlen(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(l, 10, 6, 10) , which will callbinarySearch( l, 10, 8, 10)，然后binarySearch(是 l, 10, 9, 10) , thenbinarySearch( l, 10, 10, 10)。最后一个会检查list[10] > element。但是list[10]会引发一个IndexError，因为没有t 列表中的 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，这就是递归的全部定义。

编写迭代算法而不是递归算法并没有错（除非你正在做作业并且递归是重点），但你的函数也不是迭代的——任何地方都没有循环。

（这个版本也忽略了startandend参数，但在这种情况下这不是什么大问题，因为同样，你没有做任何递归。）

无论如何，return False函数中唯一的就是 first if len(list) == 0。因此，对于任何非空列表，它要么返回True，要么返回一个数字。使用您的输入，它将返回4小于列表中点 (5) 的值的任何值，以及True其他任何值。

score 0 · Accepted Answer

def bs(list,num):    #presume that the list is a sorted list
#base case
    mid=int(len(list)/2)          # to divide the list into two parts
    if num==list[mid]:
         return True
    if len(list)==1:
       return False
#recursion
    elif num<list[mid]:           #if the num is less than mid
        return bs(list[0:mid],num)    #then omit all the nums after the mid
    elif num>list[mid]:           #if the num is greater than mid
        return bs(list[mid:],num)     # then omit all the nums before the mid
#return False
list=[1,2,3,4,5,6,7,8,9,10]
print(bs(list,20))
<<< False
 print(bs(list,4))
<<< True

score 0 · Accepted Answer

我做了这个。如果有任何错误，请纠正我。

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)

score 0 · Accepted Answer

排序列表的递归二进制搜索。

打印语句有助于了解它是如何工作的。

# n = number we are searching for
# lst = the sorted list we are searching in
# sp = list start position
# ep = list end postion
def binary_search_recursion(n: int, lst: list, sp: int = 0, ep: int = None) -> bool:
    # first time searching, start position will be 0
    # and end position will be None
    if ep is None:
        # End position equals total length minus 1 since 0 indexed
        ep = len(lst) - 1

    # get the midpoint of the list (lst)
    mid = (sp + ep) // 2
    mid_item = lst[mid]
    print(f"Start: lst[{sp}] = {lst[sp]}\nMid: lst[{mid}] = {mid_item}\nEnd: lst[{ep}] = {lst[ep]}")
    # If mid item matches the searching number then success
    if mid_item == n:
        print(f"Success!!! Number {n} found in lst[{mid}]")
        return True
    # Else if mid item is greater than number, we eliminate everything to the left and move right
    elif mid_item > n:
        new_ep = mid - 1  
        if new_ep < 0: 
            print(f"Number {n} is too low. Lowest number found is {lst[sp]}")
            return False
        else:
            print(f"Number {n} is less than mid item {mid_item}, change ep {ep} to {new_ep}.\n")
            binary_search_recursion(n, lst, sp, new_ep)
    # Else if mid item is lower than number, we eliminate everything to the right and move left
    elif mid_item < n:
        new_sp = mid + 1
        if new_sp > ep:
            print(f"Number {n} is too High. Highest number found is {lst[ep]}")
            return False
        else:
            print(f"Number {n} is greater than mid item {mid_item}, change sp {sp} to {new_sp}.\n")
            binary_search_recursion(n, lst, new_sp, ep)

测试功能：

# A sorted list
num_list = [10,20,30,40,50,60,70,80,90,100,110]

# Search for 10 in num_list
binary_search_recursion(10, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 10 is less than mid item 60, change ep 10 to 4.

Start: lst[0] = 10
Mid: lst[2] = 30
End: lst[4] = 50
Number 10 is less than mid item 30, change ep 4 to 1.

Start: lst[0] = 10
Mid: lst[0] = 10
End: lst[1] = 20
Success!!! Number 10 found in lst[0]

# Search for 110 in num_list
binary_search_recursion(110, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 110 is greater than mid item 60, change sp 0 to 6.

Start: lst[6] = 70
Mid: lst[8] = 90
End: lst[10] = 110
Number 110 is greater than mid item 90, change sp 6 to 9.

Start: lst[9] = 100
Mid: lst[9] = 100
End: lst[10] = 110
Number 110 is greater than mid item 100, change sp 9 to 10.

Start: lst[10] = 110
Mid: lst[10] = 110
End: lst[10] = 110
Success!!! Number 110 found in lst[10]


# Search for 6 in num_list
binary_search_recursion(6, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 6 is less than mid item 60, change ep 10 to 4.

Start: lst[0] = 10
Mid: lst[2] = 30
End: lst[4] = 50
Number 6 is less than mid item 30, change ep 4 to 1.

Start: lst[0] = 10
Mid: lst[0] = 10
End: lst[1] = 20
Number 6 is too low. Lowest number found is 10


# Search for 1111 in num_list
binary_search_recursion(1111, num_list)

Start: lst[0] = 10
Mid: lst[5] = 60
End: lst[10] = 110
Number 1111 is greater than mid item 60, change sp 0 to 6.

Start: lst[6] = 70
Mid: lst[8] = 90
End: lst[10] = 110
Number 1111 is greater than mid item 90, change sp 6 to 9.

Start: lst[9] = 100
Mid: lst[9] = 100
End: lst[10] = 110
Number 1111 is greater than mid item 100, change sp 9 to 10.

Start: lst[10] = 110
Mid: lst[10] = 110
End: lst[10] = 110
Number 1111 is too High. Highest number found is 110

score 0 · Accepted Answer

这是我的二分搜索递归解决方案

def recBinarySearch(arr,ele):
    if len(arr) == 0:
        return False
    else:
        mid = len(arr)/2

        if arr[mid] == ele:
            return True
        else:
            if ele < arr[mid]:
                return recBinarySearch(arr[:mid], ele)
            else:
                return recBinarySearch(arr[mid+1], ele)

score 0 · Accepted Answer

你也可以这样做：

def recursive_binary_search(list, item):
  """find the index of the given item in the list recursively"""
  low = 0
  high = len(list) - 1
  if low <= high:
    mid = low + high
    guess = list[mid]
    if guess == item:
      return mid
    if guess > item: # item must be in the first split
      return recursive_binary_search(list[low:mid], item)
    else: # check in second split otherwise
      return recursive_binary_search(list[mid:high], item)
  return None

def main():
  print(recursive_binary_search([2,3,4,5,6,7,8], 3)) #  will print 1

if __name__ == "__main__":
  main()

score 0 · Accepted Answer

您可以通过以下方式在python中实现二进制搜索。

def binary_search_recursive(list_of_numbers, number, start=0, end=None):

    # The end of our search is initialized to None. First we set the end to the length of the sequence.
    if end is None:
        end = len(list_of_numbers) - 1

    if start > end:
        # This will happen if the list is empty of the number is not found in the list.
        raise ValueError('Number not in list')

    mid = (start + end) // 2  # This is the mid value of our binary search.

    if number == list_of_numbers[mid]:
        # We have found the number in our list. Let's return the index.
        return mid

    if number < list_of_numbers[mid]:
        # Number lies in the lower half. So we call the function again changing the end value to 'mid - 1' Here we are entering the recursive mode.



        return binary_search_recursive(list_of_numbers, number, start, mid - 1)
    # number > list_of_numbers[mid]
    # Number lies in the upper half. So we call the function again changing the start value to 'mid + 1' Here we are entering the recursive mode.

    return binary_search_recursive(list_of_numbers, number, mid + 1, end)

我们应该用良好的单元测试检查我们的代码，以找到我们代码中的漏洞。

希望这对您有所帮助。

python - Python中的递归二分搜索

17 回答 17

Related

Reference