python - 在排序列表中找到大于给定数字的最小数字

Question

给定一个排序的数字列表，我需要找到大于给定数字的最小数字。考虑这个列表:

---

arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]

假设指定的数字是 320。那么，我的方法应该返回 353，因为 353 是大于 320 的最小数字。

我正在尝试使用一种稍微修改过的二进制搜索形式；但是在执行时程序进入无限循环。

---

def modBinarySearch(arr,x):
    l=len(arr)
    mid=l/2
    if arr[mid]>=x and arr[mid-1]<x:
        return arr[mid]
    elif arr[mid]>x and arr[mid-1]>x:
        modBinarySearch(arr[mid:l],x)
    else: 
        modBinarySearch(arr[0:mid],x)

N=int(raw_input())
arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]
print modBinarySearch(arr,N)

有人可以指出我做错了什么吗？

Answer 1

有一个标准模块，bisect ，这已经做到了:

In [49]: arr[bisect.bisect(arr, 320)]
Out[49]: 353

我认为这应该是搜索排序列表的首选方法。有几个examples在手册中。

至于您的实现，存在一些问题:

1. 您的递归无法正确处理小型数组。
2. 第二个分支中的切片不正确。
3. 您的函数不返回任何内容。
4. 因为arr是升序的，所以arr[mid]>x和arr[mid-1]>x等价于arr[mid-1 ]>x，暗示你没有写出你的意思

最后但同样重要的是，递归和所有切片对于这个问题来说是完全不必要的。