查找排序列表中大於給定數字的最小數字

給定一個排序的數字列表，我需要查找大於給定數字的最小數字。考慮這個名單：查找排序列表中大於給定數字的最小數字

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)

有人能指出我在做什麼錯？

來源

2012-12-02 OneMoreError

如果ARR [MID]和ARR [中旬-1]，兩者都比你的電話號碼時，你應該在ARR搜索[0：MID]，你不覺得嗎？

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

來源

2012-12-02 13:51:08 Chocolava

哦..是的。感謝您指出！ – OneMoreError

您需要從遞歸調用中返回值，而不是僅僅丟棄該信息。沒有這些，代碼的其他部分的功能並不重要。另外，你使用'1'（wun），你應該使用'l'（ell）。 – paxdiablo

如果您的列表大小將爲15，則完全丟棄二分搜索並使用順序搜索。

您會發現代碼更容易編寫，除非您需要每秒執行數百萬次，否則順序解決方案將足夠快。

如果做需要堅持使用二進制搜索，你第一步驟應該是實際回報您的遞歸調用的結果。

來源

2012-12-02 13:42:06 paxdiablo

有一個標準模塊，bisect，那已經做了這個：

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

我想這應該是去到方法用於搜索排序的列表。本手冊中有幾個examples。

至於您的實現，有一些問題：

您的遞歸不能正確處理小數組。
在第二個分支中完成的切片不正確。
你的函數不返回任何東西。
因爲arr是按升序排列，arr[mid]>x and arr[mid-1]>x相當於arr[mid-1]>x，提示你沒有寫你的意思

最後但並非最不重要的，遞歸和所有切片都是這個問題完全沒有必要的。

來源

2012-12-02 13:42:10 NPE

這使得在Python 2.7這樣的信息：'回溯（最近通話最後一個）：文件「」，第1行，在 arr [bisect.bise ct（arr，320）] NameError：name'bisect'未定義' – OneMoreError

@CSSS：你是否已經導入了'bisect'模塊？ – NPE

不..我沒有..會嘗試 – OneMoreError

如果列表進行排序：

x = range(20) 
N= 15 

for i in x: 
    if i>N: 
     print i 
     break

如果使用numpy的給出了16

：

x = np.arange(20) 
N = 15 
x[x>15][0]

給出了16

如果您正在尋找容易實現，對於你的具體問題，讓我回到這一點。

來源

2012-12-02 13:46:15 arynaq

def modBinarySearch(arr, n): 
    m = len(arr)/2 

    if arr[m] >= n and arr[m - 1] < n: 
     return arr[m] 
    elif arr[m] > n and arr[m - 1] > n: 
     return modBinarySearch(arr[:m], n) 
    else: 
     return modBinarySearch(arr[m:], n) 


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

來源

2012-12-02 13:49:40

 python 3.2 

    next(i for i in arr if i>320)

來源

2012-12-02 13:50:02 raton

的bisect module是這個你最好的選擇：

from bisect import bisect_left, bisect_right 

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


def find_lt(a, x): 
    'Find rightmost value less than x' 
    i = bisect_left(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError 

def find_gt(a, x): 
    'Find leftmost value greater than x' 
    i = bisect_right(a, x) 
    if i != len(a): 
     return a[i] 
    raise ValueError 

print find_lt(arr,320)   
print find_gt(arr,320)

打印

313 
353

來源

2012-12-03 17:32:25

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: 
     num = modBinarySearch(arr[0:mid],x) 
    else: 
     num = modBinarySearch(arr[mid:l],x) 
    return num 

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

來源

2015-04-07 19:36:28

查找排序列表中大於給定數字的最小數字

回答

相關問題