binario algoritmo di ricerca in python

Question

Sto cercando di implementare la ricerca binaria in Python e hanno scritto come segue. Tuttavia, non posso fermarlo quando needle_element è più grande dell'elemento più grande dell'array.

Potete essere d'aiuto? Grazie.

def binary_search(array, needle_element): 
    mid = (len(array))/2 
    if not len(array): 
     raise "Error" 
    if needle_element == array[mid]: 
     return mid 
    elif needle_element > array[mid]: 
     return mid + binary_search(array[mid:],needle_element) 
    elif needle_element < array[mid]: 
     return binary_search(array[:mid],needle_element) 
    else: 
     raise "Error" 

Answer 1

Nel caso in cui needle_element > array[mid], attualmente passano array[mid:] alla chiamata ricorsiva. Ma sai che array[mid] è troppo piccolo, quindi puoi passare array[mid+1:] (e aggiustare di conseguenza l'indice restituito).

Se l'ago è più grande di tutti gli elementi dell'array, eseguendolo in questo modo si otterrà un array vuoto e verrà generato un errore come previsto.

Nota: La creazione di un sub-array ogni volta che si tradurrà in cattive prestazioni per grandi array. È meglio passare invece i limiti dell'array.

Answer 2

Se si sta eseguendo una ricerca binaria, suppongo che l'array sia ordinato. Se ciò è vero, dovresti essere in grado di confrontare l'ultimo elemento dell'array con lo needle_element. Come dice il polpo, questo può essere fatto prima che inizi la ricerca.

Answer 3

Si può solo verificare che needle_element è nei limiti della matrice prima di iniziare a tutti. Ciò renderà anche più efficiente, dal momento che non dovrai fare diversi passaggi per arrivare alla fine.

if needle_element < array[0] or needle_element > array[-1]: 
    # do something, raise error perhaps? 

Answer 4

array [mid:] crea una nuova sotto-copia ogni volta che la chiami = lenta. Inoltre usi la ricorsione, che in Python è anche lenta.

Prova questa:

def binarysearch(sequence, value): 
    lo, hi = 0, len(sequence) - 1 
    while lo <= hi: 
     mid = (lo + hi) // 2 
     if sequence[mid] < value: 
      lo = mid + 1 
     elif value < sequence[mid]: 
      hi = mid - 1 
     else: 
      return mid 
    return None 

Answer 5

Sarebbe molto meglio lavorare con un lower e upper indici come Lasse V. Karlsen suggeriva in un commento alla domanda.

Questo sarebbe il codice:

def binary_search(array, target): 
    lower = 0 
    upper = len(array) 
    while lower < upper: # use < instead of <= 
     x = lower + (upper - lower) // 2 
     val = array[x] 
     if target == val: 
      return x 
     elif target > val: 
      if lower == x: # these two are the actual lines 
       break  # you're looking for 
      lower = x 
     elif target < val: 
      upper = x 

• lower < upper si fermerà una volta che si è raggiunto il numero più piccolo (dal lato sinistro)
• if lower == x: break si fermerà una volta che hai raggiunto il numero più alto (dal lato destro)

Esempio:

>>> binary_search([1,5,8,10], 5) # return 1 
1 
>>> binary_search([1,5,8,10], 0) # return None 
>>> binary_search([1,5,8,10], 15) # return None 

Answer 6

Perché non utilizzare il modulo bisect? Dovrebbe fare il lavoro che ti serve, meno codice da conservare e testare.

Answer 7

È possibile migliorare l'algoritmo come gli altri hanno suggerito, ma si deve prima occhiata al motivo per cui non funziona:

che stai ricevendo bloccato in un ciclo, perché se needle_element > array[mid], stai tra cui elemento mid nel l'array bisecato si cerca in seguito. Quindi se l'ago non si trova nell'array, alla fine si cercherà per sempre una serie di lunghezze.Passa invece al numero array[mid+1:] (è legale anche se mid+1 non è un indice valido) e alla fine chiamerai la tua funzione con un array di lunghezza zero. Quindi, len(array) == 0 significa "non trovato", non un errore. Gestirlo in modo appropriato.

Answer 8

Tutte le risposte di cui sopra sono vere, ma penso che sarebbe utile condividere il mio codice

def binary_search(number): 
numbers_list = range(20, 100) 
i = 0 
j = len(numbers_list) 
while i < j: 
    middle = int((i + j)/2) 
    if number > numbers_list[middle]: 
     i = middle + 1 
    else: 
     j = middle 
return 'the index is '+str(i) 

Answer 9

Restituisce l'indice di chiave nella matrice utilizzando ricorsiva.

round() è una funzione converti float in intero e rende il codice veloce e passa al caso previsto [O (logn)].

A=[1,2,3,4,5,6,7,8,9,10] 
low = 0 
hi = len(A) 
v=3 
def BS(A,low,hi,v): 
    mid = round((hi+low)/2.0) 
    if v == mid: 
     print ("You have found dude!" + " " + "Index of v is ", A.index(v)) 
    elif v < mid: 
     print ("Item is smaller than mid") 
     hi = mid-1 
     BS(A,low,hi,v) 
    else : 
     print ("Item is greater than mid") 
     low = mid + 1 
     BS(A,low,hi,v) 
BS(A,low,hi,v) 

Answer 10

def binary_search(array, target): 
    low = 0 
    mid = len(array)/2 
    upper = len(array) 

    if len(array) == 1: 
     if array[0] == target: 
      print target 
      return array[0] 
     else: 
      return False 
    if target == array[mid]: 
     print array[mid] 
     return mid 
    else: 
     if mid > low: 
      arrayl = array[0:mid] 
      binary_search(arrayl, target) 

     if upper > mid: 
      arrayu = array[mid:len(array)] 
      binary_search(arrayu, target) 

if __name__ == "__main__": 
    a = [3,2,9,8,4,1,9,6,5,9,7] 
    binary_search(a,9) 

Answer 11

Senza gli indici inferiori/superiori questo dovrebbe anche fare:

def exists_element(element, array): 
    if not array: 
     yield False 

    mid = len(array) // 2 
    if element == array[mid]: 
     yield True 
    elif element < array[mid]: 
     yield from exists_element(element, array[:mid]) 
    else: 
     yield from exists_element(element, array[mid + 1:]) 

Answer 12

Questa è una soluzione ricorsiva coda, io che questo sia pulito che copiare matrici parziali e poi tenere traccia degli indici per la restituzione:

def binarySearch(elem, arr): 
    # return the index at which elem lies, or return false 
    # if elem is not found 
    # pre: array must be sorted 
    return binarySearchHelper(elem, arr, 0, len(arr) - 1) 

def binarySearchHelper(elem, arr, start, end): 
    if start > end: 
     return False 
    mid = (start + end)//2 
    if arr[mid] == elem: 
     return mid 
    elif arr[mid] > elem: 
     # recurse to the left of mid 
     return binarySearchHelper(elem, arr, start, mid - 1) 
    else: 
     # recurse to the right of mid 
     return binarySearchHelper(elem, arr, mid + 1, end)