¿Cuál sería el tiempo de ejecución si utilizara la búsqueda binaria y luego la búsqueda lineal en un array ordenado?

Por ejemplo, tengo un arreglo ordenado de x cantidad de pares clave-valor(tuplas). Tengo un método llamado range que toma dos argumentos, el primero es la primera clave a encontrar y el segundo es la última clave a encontrar. Esta función devuelve todas las claves entre las dos. Por lo tanto, range utiliza búsqueda binaria para encontrar el primer elemento y una vez que lo hace, utiliza búsqueda lineal para avanzar hasta que se encuentre la última clave. Pensé que todo esto tendría un tiempo de ejecución de O(log(n)) pero ahora dudo de mí mismo ya que tarda más en ejecutarse de lo que me gustaría. Entonces mi pregunta es ¿cuál sería el tiempo de ejecución de esta función, ya que parece que estoy equivocado?