binario algoritmo de búsqueda en Python

Question

estoy tratando de poner en práctica la búsqueda binaria en Python y haber escrito la siguiente manera. Sin embargo, no puedo detenerlo cada vez que needle_element es más grande que el elemento más grande de la matriz.

puede ayudar? Gracias.

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

En el caso de que needle_element > array[mid], se pasa actualmente array[mid:] a la llamada recursiva. Pero sabe que array[mid] es demasiado pequeño, por lo que puede pasar array[mid+1:] en su lugar (y ajustar el índice devuelto en consecuencia).

Si la aguja es más grande que todos los elementos de la matriz, haciendo de esta manera con el tiempo le dará una matriz vacía, y se produce un error como se esperaba.

Nota: La creación de un sub-conjunto cada vez dará lugar a un mal desempeño para grandes matrices. Es mejor pasar en los límites de la matriz en su lugar.

Answer 2

Si está haciendo una búsqueda binaria, supongo que la matriz está ordenada. Si eso es cierto, debería poder comparar el último elemento de la matriz con el needle_element. Como dice el pulpo, esto se puede hacer antes de que comience la búsqueda.

Answer 3

Sólo puede comprobar para ver que needle_element está en los límites de la matriz antes de iniciar en absoluto. Esto lo hará más eficiente también, ya que no tendrá que hacer varios pasos para llegar al final.

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

Answer 4

array [mediados:] crea un nuevo sub-copia cada vez que llaman = lento. También usas recursion, que en Python también es lenta.

Prueba esto:

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

Sería mucho mejor trabajar con una lower y upper índices como Lasse V. Karlsen se sugiere en un comentario a la pregunta.

Este sería el código:

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 se detendrá una vez que haya alcanzado el número más pequeño (del lado izquierdo)
• if lower == x: break se detendrá una vez que haya alcanzado el número más alto (desde el lado derecho)

Ejemplo:

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

¿Por qué no utilizar el módulo bisecado? Debería hacer el trabajo que necesita, menos código para que pueda mantener y probar.

Answer 7

Usted puede mejorar su algoritmo como los otros sugirieron, pero primero vamos a ver por qué no funciona:

Te estás atrapado en un bucle porque si needle_element > array[mid], que está incluida en el elemento de mid matriz bisecada que busca a continuación. Entonces, si la aguja no está en la matriz, finalmente buscará una matriz de longitud uno para siempre.Pase array[mid+1:] en su lugar (es legal incluso si mid+1 no es un índice válido), y eventualmente llamará a su función con una matriz de longitud cero. Entonces len(array) == 0 significa "no encontrado", no es un error. Manejarlo apropiadamente.

Answer 8

Todas las respuestas anteriores son verdaderas, pero yo creo que ayudaría a compartir mi código

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

Devuelve el índice de clave en la matriz utilizando recursiva.

round() es una función que convierte float en entero y hace que el código sea rápido y va al caso esperado [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

Sin los índices inferior/superior esto también debe hacer:

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

Ésta es una solución recursiva cola, creo que esto es más limpio que la copia de las matrices parciales y luego hacer el seguimiento de los índices de devolución:

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)