Znajdź najmniejszą liczbę, która jest większa niż podana liczba w posortowanej liście

Question

Biorąc posortowaną listę liczb, muszę znaleźć najmniejszą liczbę, która jest większa niż podana liczba. Rozważmy tę listę:

---

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

powiedzieć, że podana liczba jest 320. Następnie, moja metoda powinna powrócić 353 a 353 jest najmniejszą liczbą większą niż 320.

Próbuję użyć nieco zmodyfikowany forma wyszukiwania binarnego; jednak w trakcie wykonywania program przechodzi w nieskończoną pętlę.

---

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) 

Czy ktoś może wskazać, co robię źle?

Answer 1

Jeśli arr [mid] i arr [mid-1], oba są większe niż liczby, należy szukać w arr [0: Średni], nie sądzisz?

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

Answer 2

Jeśli rozmiar twoich list ma wynosić 15, porzuć całkowicie wyszukiwanie binarne i użyj wyszukiwania sekwencyjnego.

Kod ten jest znacznie łatwiejszy w pisaniu i, o ile nie trzeba go wykonywać wiele milionów razy na sekundę, sekwencyjne rozwiązanie będzie wystarczająco szybkie.

Jeśli zrobić trzeba trzymać przy wyszukiwaniu binarnym, Twój pierwszy krokiem powinno być rzeczywiście powrócić wyniki swoich rekurencyjnych wywołań.

Answer 3

Jest to moduł standardowy, bisect, że robi to już:

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

myślę, że to powinno być przejdź do metody poszukiwania posortowanych list. W instrukcji jest kilka examples.

Co do implementacji, istnieje szereg problemów:

1. Twój rekurencji nie obsługuje małe tablice poprawnie.
2. Krojenie wykonane w drugim oddziale jest nieprawidłowe.
3. Twoja funkcja niczego nie zwraca.
4. Ponieważ arr jest w porządku rosnącym, arr[mid]>x and arr[mid-1]>x jest równoważna arr[mid-1]>x, co sugeruje, że nie napisać, co oznaczało

Last but not least, rekurencję i wszystko, krojenie są całkowicie zbędne dla tego problemu.

Answer 4

jeśli lista jest posortowana:

x = range(20) 
N= 15 

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

Daje 16.

przypadku korzystania numpy:

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

daje 16.

Jeśli szukałeś prostych wdrożeń, dla twojego konkretnego problemu, pozwól mi wrócić do tego.

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

bisect module jest najlepszym wyborem do tego:

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) 

drukuje

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)