¿Cómo se puede encontrar un elemento usando la búsqueda binaria en una función recursiva en C?
Escribí este código corto para encontrar la ubicación del elemento x en un arreglo ordenado (de mayor a menor) con complejidad O(log n). “n” y “arr” representan los límites del arreglo.
Sin embargo, parece que no funciona correctamente. ¿Alguna sugerencia?
int ex2_1(int *arr, int n, int key)
{
if (n == 0)
return -1;
if (arr[n / 2] == key)
return n / 2;
if (arr[n / 2] > key)
return ex2_1(arr + n / 2 + 1, n - n / 2 - 1, key);
return ex2_1(arr, n / 2, key);
}
Para int arr[] = { 9, 7, 7, 5, 3, 3, 3, 1 };, int n = 8 e int key = 3, obtengo 4 cuando debería obtener 5.
davy.ai
El problema parece estar en la tercera declaración ‘if’ donde debería devolver el resultado de la llamada recursiva con los parámetros correctos. Como el arreglo está ordenado en orden descendente, si el elemento del medio es mayor que la clave, significa que la clave está en el lado derecho del arreglo, por lo que la llamada recursiva debería hacerse con el lado derecho del arreglo que comienza desde
arr + n / 2 + 1y con la longitud de los elementos restantes que esn - n / 2 - 1. Por otro lado, si el elemento del medio es menor que la clave, significa que la clave está en el lado izquierdo del arreglo, por lo que la llamada recursiva debería hacerse con el lado izquierdo del arreglo que comienza desdearry con la longitud de la primera mitad que esn / 2. Por lo tanto, el código corregido debería verse así:Después de hacer esta corrección, la función debería funcionar correctamente y devolver el índice correcto de la clave en un arreglo ordenado.