Búsqueda binaria en una lista ordenada con duplicados
Para aprender los algoritmos de dividir y conquistar, estoy implementando una función en Python llamada binary_search
que obtendrá el índice de la primera aparición de un número en una lista ordenada no vacía (los elementos de la lista son enteros no negativos y no decrecientes). Por ejemplo, binary_search([1,1,2,2,3,4,4,5,5], 4) == 5
, binary_search([1,1,1,1,1], 1) == 0
y binary_search([1,1,2,2,3], 5) == -1
, donde -1
significa que el número no se puede encontrar en la lista.
A continuación se encuentra mi solución. Aunque la solución a continuación pasó todas las pruebas que creé manualmente, falló en casos de prueba de un probador de caja negra. ¿Podría alguien decirme qué hay de malo con el código siguiente?
def encontrar_primer_indice(A, bajo, alto, clave):
if A[bajo] == clave:
return bajo
if bajo == alto:
return -1
medio = bajo + (alto - bajo) // 2
if A[medio] == clave:
if A[medio - 1] == clave:
return encontrar_primer_indice(A, bajo, medio - 1, clave)
else:
return medio
if clave < A[medio]:
return encontrar_primer_indice(A, bajo, medio - 1, clave)
else:
return encontrar_primer_indice(A, medio + 1, alto, clave)
def binary_search(keys, number):
indice = encontrar_primer_indice(A=keys, bajo=0, alto=len(keys) - 1, clave=number)
return(indice)
davy.ai
Parece haber un problema con el parámetro pasado a la función
find_first_index
. El parámetro se pasa comoA=keys
, pero la definición de la función tomaA
como un parámetro, mientras que el parámetro pasado eskeys
. Esto podría estar causando que la función no encuentre el índice correcto y falle algunos casos de prueba. Para solucionar esto, el parámetro debería ser pasado comoA
.