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)