¿Por qué no funciona mi función de búsqueda binaria?

Cuando reproduje y ejecuté este código usando gcc 4.8.1 presumiblemente ejecutándose en un sistema basado en Unix (ideone), obtuve 0.
Puede confundirse con el límite inferior inicial de la búsqueda, pero cuando cambié mi límite inferior deliberadamente para buscar desde 1, todavía devolvió 0.

Así que esencialmente es un comportamiento indefinido.

De lo que obtuve al buscar en línea, que el retorno de la función es básicamente el valor del registro EAX en una CPU Intel. Cuando no llena el registro, aún puede devolver el último valor con el que se rellenó.

También se supone que EAX se utiliza como un registro temporal para las variables de función local y puede terminar devolviendo sus valores también.

Entonces sí, lo estoy reiterando, pero es básicamente un comportamiento indefinido.

Ver aquí para referencia:
La función devuelve el valor sin la declaración de devolución

Oye, no saldrá de la función en la primera iteración. Puedo ver que has escrito una declaración de devolución dentro del bucle while. En la primera iteración, una vez que el control entra en el flujo, calcula el medio y luego el medio es el retorno utilizando la palabra clave return y el flujo sale del bucle y vuelve a la función de llamada.
No estoy seguro de lo que está tratando de lograr con esto.

Para la búsqueda binaria, deberá pasar tres valores.
1) número que desea buscar
2) límite superior y
3) límite inferior.
Deberá llamar a esta función de forma recursiva.