Enfrentando problemas en la búsqueda binaria en c
#include
int bsearch(int ar[],int n,int key)
{
int s = 0;
int e = n – 1;
while(s <= e) {
int mid = (e + s) / 2;
if(mid == key) {
return mid;
}
else if(key < mid) {
e = mid - 1;
}
else if(key > mid) {
s = mid + 1;
}
}
return -1;
}
He creado la función para la búsqueda binaria
int main()
{
int n, key;
printf(“Ingrese cantidad de elementos del arreglo: “);
scanf(“%d”, &n);
int ar[n];
for(int i = 0; i < n; i++) {
printf(“ar[%d]= “, i);
scanf(“%d”, &ar[i]);
}
printf(“Ingrese un valor para buscar: “);
scanf(“%d”, &key);
printf(“%d es el índice”, bsearch(ar, n, key));
return 0;
}
Después ingresé un arreglo ordenado pero con repeticiones. Se muestra en la siguiente imagen.
La salida muestra que 3 es el índice.
Sin embargo, debería mostrar que 6 es el índice.
davy.ai
El problema con el código está en la condición
if (mid==key)
dentro del bucle while. Aquí estamos comprobando si el elemento central actual es igual a la clave. Sin embargo, dado que el array puede contener repeticiones, deberíamos comprobar el elemento en el índice medio con la clave, en lugar del índice en sí mismo.Para solucionar el problema, deberíamos reemplazar
if (mid == key)
conif (ar [mid] == key)
. Esto asegurará que estamos comparando los elementos correctos en el array.El código corregido para la función de búsqueda binaria sería:
Con esta corrección, el código debería devolver el índice correcto para los elementos repetidos en el array.</ar[mid]){>