Python中的递归二分查找

Recursion binary search in Python

提问by user2898221

I have a list with numbers from 0-9:

我有一个数字从 0-9 的列表：

mylist = list(range(10))

I am getting an error with the division command to get mid:

我在使用除法命令时遇到错误以获取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

and if I wanted to return Truehow would I write that on top of return binary_search(mylist, element, mymin, mid-1)?

如果我想返回True，我将如何在上面写return binary_search(mylist, element, mymin, mid-1)？

回答by abarnert

Your first one won't even get started, because list(mid)will immediately raise a TypeError: 'list' object is not callable.

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

If you fix that (by using list[mid]), your next problem is that you ignore the minand maxarguments you receive, and instead set them to 0and len(list)-1each time. So, you will infinitely recurse (until you eventually get a RecursionErrorfor hitting the stack limit).

如果你解决了这个问题（通过使用list[mid]），你的下一个问题是你忽略了你收到的min和max参数，而是每次都将它们设置为0和len(list)-1。因此，您将无限递归（直到您最终获得RecursionError达到堆栈限制的 a）。

Think about it: the first call to binarySearch(l, 5, 0, 10)recursively calls binarySearch(l, 5, 0, 4). But that call ignores that 4and acts as if you'd passed 10, so it recursively calls binarySearch(l, 5, 0, 4). Which calls binarySearch(l, 5, 0, 4). And so on.

想一想：第一次调用binarySearch(l, 5, 0, 10)递归调用binarySearch(l, 5, 0, 4). 但是该调用忽略了这一点4，就像您通过了一样10，因此它递归地调用binarySearch(l, 5, 0, 4). 其中调用binarySearch(l, 5, 0, 4). 等等。

If you fix that (by removing those two lines), you've got another problem. When you give it the number 10, binarySearch(l, 10, 0, 10)will call binarySearch(l, 10, 6, 10), which will callbinarySearch(l, 10, 8, 10), then binarySearch(l, 10, 9, 10), thenbinarySearch(l, 10, 10, 10). And that last one will check list[10] > element. But list[10]is going to raise an IndexError, because there aren't 11 elements in the list.

如果你解决了这个问题（通过删除这两行），你就会遇到另一个问题。当你给它数字时10，binarySearch(l, 10, 0, 10)会调用binarySearch(l, 10, 6, 10) , which will callbinarySearch( l, 10, 8, 10), then binarySearch(l, 10, 9, 10) , thenbinarySearch( l, 10, 10, 10)。最后一个会检查list[10] > element。但是list[10]会引发一个IndexError，因为没有t 列表中的 11 个元素。

And once you fix that off-by-one error, there are no problems left. The problem you asked about cannot possibly ever occur. Here's an example run:

一旦你解决了那个一一错误，就没有问题了。你问的问题不可能永远发生。这是一个示例运行：

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

---

---

Your second version isn't recursive. bSearchnever calls bSearch, and that's the whole definition of recursion.

你的第二个版本不是递归的。bSearch从不调用bSearch，这就是递归的全部定义。

There's nothing wrong with writing an iterative algorithm instead of a recursive algorithm (unless you're doing a homework problem and recursion is the whole point), but your function isn't iterative either—there are no loops anywhere.

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

(This version also ignores the startand endarguments, but that's not as much of a problem in this case, because, again, you're not doing any recursion.)

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

Anyway, the only return Falsein the function is in that first if len(list) == 0. So, for any non-empty list, it's either going to return True, or a number. With your input, it will return 4for anything less than the value at the midpoint of the list (5), and Truefor anything else.

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

回答by sherwoor

Your problem here is that you're redeclaring min and max in each loop, so although it should be recursive, passing in a new min or max each time, this isn't in fact happening.

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

You can solve this by using defaults in the arguments:

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

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

If you're not familiar with the syntax on line 2, max = max or len(list)-1 max will be set to len(list)-1 only if max is not passed in to the method.

如果您不熟悉第 2 行的语法，仅当 max 未传入方法时，max = max 或 len(list)-1 max 才会设置为 len(list)-1。

So you can call the method simply using:

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

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

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

回答by GrantJ

The first solution looks wrong because it doesn't index the list.

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

This problem tripped me up too the first time I wrote a solution so be sure to test your algorithm well.

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

Here's what I ended up with:

这是我的结果：

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)

And when I test it, the answers look correct:

当我测试它时，答案看起来是正确的：

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 has a library module for just this kind of thing named bisect.

顺便说一句，Python 有一个名为bisect的库模块。

回答by Gluamice

Just another answer to the same question:

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

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)

回答by Sonal Dubey

You can make use of list slicing too.

您也可以使用列表切片。

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)

However, note that list slicing introduces additional complexity.

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

回答by Vividh S V

There are a lot of solutions here already. Below is one more solution without slicing and that just requires element and list as arguments:

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

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

回答by Norah Borus

Recursive solution:

递归解决方案：

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)

Iterative solution:

迭代解决方案：

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

回答by CASE

I made this one. Correct me if there's any bug.

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

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)

回答by Shane FAN

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

回答by Gurupratap

You can implement binary search in python in the following way.

您可以通过以下方式在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)

We should check our code with good unittest to find loop holes in our code.

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

Hope this helps you.

希望这对你有帮助。