Trova il numero più piccolo che è maggiore di un dato numero in un elenco ordinato

Question

Dato un elenco ordinato di numeri, ho bisogno di trovare il numero più piccolo che è maggiore di un dato numero. Considerate questo elenco:

---

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

Pronunciare il numero specificato è 320. Poi, il mio metodo dovrebbe restituire 353 come 353 è il più piccolo numero maggiore di 320.

Sto cercando di usare un po 'modificata forma di ricerca binaria; comunque durante l'esecuzione il programma va in loop infinito.

---

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) 

Qualcuno può sottolineare quello che sto facendo di sbagliato?

Answer 1

Se arr [metà] e arr [metà 1], entrambi sono più grande di tuo numero, occorre eseguire la ricerca in arr [0: metà], non credi?

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

Answer 2

Se la dimensione degli elenchi sarà 15, eliminare la ricerca binaria e utilizzare una ricerca sequenziale.

Troverai il codice molto più facile da scrivere e, a meno che non sia necessario farlo milioni di volte al secondo, la soluzione sequenziale sarà più che sufficiente.

Se fai necessità di attaccare con la ricerca binaria, la tua prima passo dovrebbe essere quello di tornare in realtà i risultati delle vostre chiamate ricorsive.

Answer 3

C'è un modulo standard, bisect, che fa questo già:

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

credo che questo dovrebbe essere il go-to metodo di ricerca elenchi ordinati. Ci sono alcuni examples nel manuale.

Per quanto riguarda l'implementazione, v'è una serie di problemi:

1. tuo ricorsione non gestisce correttamente piccoli array.
2. L'affettamento eseguito nel secondo ramo non è corretto.
3. La tua funzione non restituisce nulla.
4. Perché arr è in ordine crescente, arr[mid]>x and arr[mid-1]>x è equivalente a arr[mid-1]>x, suggerendo non hai scritto che cosa avete significato

Ultimo ma non meno importante, la ricorsione e tutto ciò che affettare è completamente inutile per questo problema.

Answer 4

Se l'elenco è ordinato:

x = range(20) 
N= 15 

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

Dà 16.

Se si utilizza NumPy:

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

Dà 16.

Se stavate cercando per una facile implementazione, per il tuo problema specifico, lasciami tornare su questo.

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

Il bisect module è la scelta migliore per questo:

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) 

stampe

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)