Estoy tratando de implementar la búsqueda binaria en python y he escrito como sigue. Sin embargo, no puedo hacer que deje de siempre needle_element es mayor que el mayor elemento de la matriz.

Puede usted 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"
Me gustaría tratar de evitar la creación de un montón de copias parciales de la matriz, y pasar un superior e inferior del índice de lugar. A continuación, simplemente detener, si es inferior>parte superior.
Puede que desee ver binario de búsqueda en python
Si el propósito de esto es académico de la comprensión de binsearch, realmente no puedo ayudar, pero si el propósito de este código es que permite ser utilizado: nunca rollo de su propia binsearch. Siempre utilizar infinidad de publicaciones adoptado, y prefereably de edad, la implementación de la biblioteca, e incluso entonces ser muy cuidadoso, binseach es muy difícil de obtener el derecho en todos los edgecases.

OriginalEl autor AbdulFattah Popoola | 2012-02-29

14 Comentarios

  1. 8

    En el caso de que needle_element > array[mid], que actualmente pasan array[mid:] a la llamada recursiva. Pero usted sabe que array[mid] es demasiado pequeño, así que usted puede pasar array[mid+1:] lugar (y ajustar el índice devuelta en consecuencia).

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

    Nota: la Creación de una sub-matriz cada vez va a resultar en un rendimiento malo para matrices grandes. Es mejor pasar en los límites de la matriz en su lugar.

    El buen desempeño de la nota; es importante para el OP considerar que

    OriginalEl autor interjay

  2. 15

    Sería mucho mejor trabajar con un lower y upper índices como Lasse V. Karlsen estaba sugiriendo 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 han alcanzado el número más pequeño (del lado izquierdo)
    • if lower == x: break se detendrá una vez que haya alcanzado el mayor número (del 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
    Esto no funciona. Intente una lista: [7,9,2,4,8,6,5,1,8,5,3].
    búsqueda binaria trabaja en una lista ordenada, el tuyo no…
    Usted podría hacer x = (lower + upper) // 2

    OriginalEl autor Rik Poggi

  3. 6

    ¿Por qué no utilizar el bisecar módulo? Se debe hacer el trabajo que usted necesita—menos código para usted para mantener y probar.

    bisecar.bisect_right( a, b) -> va a ser difícil hacer mejor velocidad sabio

    OriginalEl autor Pierce

  4. 6

    matriz[media:] crea un nuevo sub-copia cada vez que se llame = lento. También se utiliza la recursividad, que en Python es lento, demasiado.

    Intente 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
    No sólo la recursividad es lento, realmente va a explotar en la cara si la matriz es lo suficientemente largo, ya que Python no tiene cola recursividad de optimización y se ejecute fuera de los marcos de pila dado una lo suficientemente grande como matriz de entrada.
    ad «lo suficientemente grande como matriz de entrada» – dado que estamos hablando de «binario» de búsqueda y CPython por defecto límite de recursividad 1000 (se puede establecer más por sys.setrecursionlimit) estamos hablando acerca de las matrices de tamaños de hasta 2**1000, también conocido como ~10^300…

    OriginalEl autor Ecir Hana

  5. 2

    Usted puede mejorar su algoritmo como el que en otros se sugiere, pero veamos primero por qué no funciona:

    Usted está consiguiendo atrapado en un bucle porque si needle_element > array[mid], está incluido el elemento mid en la dividida matriz de búsqueda siguiente. Así que si la aguja no está en la matriz, que finalmente va a ser la búsqueda de una matriz de longitud de uno para siempre. Pasar array[mid+1:] lugar (es legal incluso si mid+1 no es un índice válido), y que finalmente va a llamar a la función con una matriz de longitud cero. Así len(array) == 0 significa «no encontrado», no un error. Manejar de forma adecuada.

    OriginalEl autor alexis

  6. 1
    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)

    OriginalEl autor user1342336

  7. 0

    Si usted está haciendo una búsqueda binaria, estoy suponiendo que el array está ordenado. Si que es cierto que deben ser capaces de comparar el último elemento de la matriz a la needle_element. Como el pulpo dice, esto se puede hacer antes de que empieza la búsqueda.

    OriginalEl autor macduff

  8. 0

    Sólo puede comprobar que needle_element está en los límites de la matriz antes de comenzar. Esto hará que sea más eficiente también, ya que usted no tiene que hacer varios pasos para llegar a la final.

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

    OriginalEl autor Donald Miner

  9. 0

    Todas las respuestas anteriores son verdaderas , pero 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)

    OriginalEl autor Maysara Alhindi

  10. 0

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

    round() es una función de convertir flotante a entero y hacer que el código sea rápido y va a la espera de caso[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)

    OriginalEl autor Anıl Selvi

  11. 0

    Sin la parte inferior/superior índices esto también se 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:])

    OriginalEl autor nettrino

  12. 0

    Esta es una cola recursiva solución, creo que esto es más limpio que el de la copia parcial de las matrices y, a continuación, mantener un 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)

    OriginalEl autor Sean

  13. 0

    El Uso De Recursividad:

    def binarySearch(arr,item):
        c = len(arr)//2
        if item > arr[c]:
           ans = binarySearch(arr[c+1:],item)
           if ans:
              return binarySearch(arr[c+1],item)+c+1
        elif item < arr[c]:
           return binarySearch(arr[:c],item)
        else:
           return c
    
    binarySearch([1,5,8,10,20,50,60],10)

    OriginalEl autor Aysun

  14. 0

    Devolver un booleano si el valor está en la lista.

    Capturar el primer y el último índice de la lista, bucle y dividir la lista de la captura de la mitad del valor.
    En cada bucle que va a hacer lo mismo, y luego comparar si el valor de entrada es igual a la mitad del valor.

    def binarySearch(array, value):
      array = sorted(array)
      first = 0
      last = len(array) - 1
    
      while first <= last:
        midIndex = (first + last) // 2
        midValue = array[midIndex]
    
        if value == midValue:
          return True
        if value < midValue:
          last = midIndex - 1
        if value > midValue:
          first = midIndex + 1
      return False

    OriginalEl autor Israel Manzo

Dejar respuesta

Please enter your comment!
Please enter your name here