Suchen Sie die kleinste Zahl, die größer als eine gegebene Zahl in einer sortierten Liste ist

Question

Angesichts einer sortierten Liste von Zahlen, muss ich die kleinste Zahl finden, die größer als eine gegebene Zahl ist. Betrachten Sie diese Liste:

---

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

Sagen Sie die angegebene Nummer 320 ist dann sollte meine Methode zurückgeben 353 wie 353 die kleinste Zahl größer als 320.

Ich versuche, eine leicht modifizierte zu verwenden Form der binären Suche; Bei der Ausführung geht das Programm jedoch in die Endlosschleife.

---

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) 

Kann jemand darauf hinweisen, was ich falsch mache?

Answer 1

Wenn arr [Mitte] und arr [Mitte 1], die beide größer sind als Ihre Nummer, sollten Sie in arr suchen [0: Mitte], nicht wahr?

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

Answer 2

Wenn die Größe Ihrer Listen 15 beträgt, lassen Sie die binäre Suche komplett fallen und verwenden Sie eine sequenzielle Suche.

Sie werden feststellen, dass der Code viel einfacher zu schreiben ist. Wenn Sie dies nicht viele Millionen Mal pro Sekunde tun müssen, ist die sequenzielle Lösung mehr als schnell genug.

Wenn Sie Notwendigkeit, mit der binären Suche bleiben tun , Ihr erster Schritt sollte sein, um tatsächlich die Ergebnisse Ihrer rekursive Anrufe zurückzukehren.

Answer 3

Es ist ein Standardmodul, bisect, dass dies bereits tut:

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

Ich denke, das für die Suche sortierte Listen die Go-to-Methode sein sollte. Es gibt ein paar examples im Handbuch.

In Bezug auf die Implementierung, gibt es eine Reihe von Problemen:

1. Ihre Rekursion richtig kleine Arrays nicht verarbeitet.
2. Das Schneiden im zweiten Zweig ist falsch.
3. Ihre Funktion gibt nichts zurück.
4. Da arr aufsteigend ist, ist arr[mid]>x and arr[mid-1]>x entspricht arr[mid-1]>x, was darauf hindeutet Sie nicht schreiben, was Sie

Last but not least soll, Rekursion und all das Aufschneiden sind für dieses Problem völlig unnötig.

Answer 4

Wenn die Liste sortiert:

x = range(20) 
N= 15 

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

Gibt 16.

Wenn numpy mit:

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

Gibt 16.

Wenn Sie für eine einfache Implementierungen gesucht haben, für Ihr spezifisches Problem, lassen Sie mich darauf zurückkommen.

Answer 5

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

Answer 6

 python 3.2 

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

Answer 7

Die bisect module ist die beste Wahl für diese:

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) 

druckt

313 
353  

Answer 8

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)