Tu problema está en el bucle while dentro de la condición de coincidencia...

Pasando 144, se localiza en el penúltimo índice, le pides que localiza los que sean iguales para tratar de devolver el último de ellos con el mismo valor, hay uno más... pero en tu bucle sigues aumentando el índice sin comprobar si se alcanzó el final del array.

Una mejor manera es hacer justo lo contrario (en cierto modo), devolver el índice donde debiera ubicarse si no existe, o el primer lugar donde exista. Dado que el índice 0, siempre existe, si resulta ser menor que todo el array o igual al primer elemento, devuelve 0, con lo cual siempre estará bien ubicado, y no incurres en error.

Mejor aún es simplemente devolver ese índice, sin tratar de buscar los que le preceden o siguen de igual valor... ya si por ejemplo se tratara de insertar un elemento, que más da, que se inserte el primero, el 5 de 10 o el 10 (si antes eran 9). tu al final tras la inserción tendrías (por ejemplo):
...x, x, x, x 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, y, y, y, y...
Cuál de esos 144 es el que tu has añadido?. No suele importar si no tiene más datos asociados.


Si a pesar de todo deseas mantener tu código, lo comento en detalle...
Observa el problema paso a paso... el array tiene 15 elementos que van del indice 0 al 14.
Hay dos casos, que accedas primero al indice 13 o primero al indice 14...

A - En el indice 13 localiza, el valor 144: luego entra en el bucle, ya que el índice 13 es menor que el size-1 del array. Ahora evalúa si el valor es menor que el recién enconttrado (en el índice 13), no es verdad luego incrementa centro y regresa a la condición del bucle... ahora se alcanzó el límite del bucle, lo que impide seguir ejecutándolo, sale del bucle y luego del externo y por tanto devuelve -1

B - En el indice 14 localiza el valor 144: El bucle while impide entrar al mismo, pues es el último en el array, sale del bucle interno y luego del externo y devuelve -1

Tú codigo funcionaría, si tras dichos valores hubiera un elemento más (mayor lógicamente que los previos). Pero entonces tendría el mismo problema con ése... es decir siempre con el último (o últimos, si son iguales).

Tu código debe quedar así:

while(bajo <= alto){
    centro = (bajo + alto) / 2;
    if(clave == array[centro]){
        centro++;
	while(centro <= (size - 1)){
	    if(clave < array[centro])
	        return centro;
	    centro++;
	}  
        return centro;
    }else if(clave < array[centro])
	alto = centro - 1;
    else
	bajo = centro + 1;    
}
return -1;
 

Nota las dos líneas (4 y 10) que he añadido y la 5 modificado.

Te paso la original y una variación que devuelve el indice del primer número mayor y en caso contrario devuelve el tamaño del vector size . (Esto es más natural que -1..)

Tu ya lo cambias si quieres.

#include <iostream>
 
int binary_search(const int V[], const int N, const int elem);
int binary_search2(const int V[], const int N, const int elem);
 
#define size 15
 
int main(){
 
	int numero;
	int array[size] = {0, 1, 1, 2, 3, 5, 8, 13, 13, 21, 34, 55, 89, 144, 144};
 
	std::cout << "Buscar numero: ";
	std::cin >> numero;
 
	const int index = binary_search2(array, size,numero);
	if (index == size)
		std::cout << "No hay elemento mayor a " << numero << std::endl; 
	else
		std::cout << "Array[" << index << "] = " << array[index] << std::endl;
 
	return 0;
}
 
 
#define h ((i+j)/2)
 
/* P: N >= 1, V sorted , elem in V*/
/* original */
int binary_search(const int V[], const int N, const int elem) 
{
    int i,j;
    i=0;
    j=N; 
    while (V[h]!= elem) 
        if (V[h]>elem) j=h;
        else i=h+1;
    return h;
}
 
/* P: N >= 1, V sorted , elem in V*/
/* Variation */
int binary_search2(const int V[], const int N, const int elem)
{
    int i,j;
    i=0;
    j=N; 
	// I : 0<= i < j <= N and V[i] <= V[elem] <= V[j-1]
    while (V[h]!= elem || (h<N-1 && V[h]==V[h+1]))  // <= B: Changes.
        if (V[h]>elem) j=h;
        else i=h+1;
    return h+1; // V[h] points to element. 
}
 

EDIT: La linea
tenía un error tipográfico. (Crédito: jca1)

La salida da



No quiero abrumar con formalismos. Fijate especialmente en:

• la precondicion P: el array ordenado y el numero que pases tiene que existir
• la parada B: A la derecha de h hay uno mayor,  o esta en ultima posicion

Un saludo.

  Gracias jca1!

1000 veces lo hubiera visto y 1000 veces no me habría dado cuenta del error tipográfico.

Corrijo en el original , poniendo EDIT y dando crédito.

Si tienes razon! Me olvide de acotar que esa solucion no es eficiente por eso. No pude modificarla asi que muy bien aclarado, igual no es necesario ya.
Gracias dijsktra!

Este es el algoritmo referido:


Saludos!