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

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

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

至于你的实现,有很多问题:

1. 您的递归不能正确处理小数组.
2. 在第二个分支中完成的切片是不正确的.
3. 你的功能不会返回任何东西.
4. 因为arr是按升序排列,arr[mid]>x and arr[mid-1]>x相当于arr[mid-1]>x,暗示你没有写出你的意思

最后但并非最不重要的是,递归和所有切片对于这个问题完全没有必要.

Answer 2

如果列表的大小为15,则完全抛弃二进制搜索并使用顺序搜索.

您会发现代码更容易编写,除非您需要每秒执行数百万次,否则顺序解决方案将足够快.

如果你做需要坚持使用二进制搜索,你的第一个步骤应该是实际回报您的递归调用的结果.

Answer 3

如果arr [mid]和arr [mid-1]两者都大于你的数字,你应该搜索arr [0:mid],你不觉得吗？

 elif arr[mid]>x and arr[mid-1]>x:
    modBinarySearch(arr[0:mid],x)
else: 
    modBinarySearch(arr[mid:1],x)