Escribiendo una búsqueda binaria recursiva en C

He encontrado el siguiente código en línea,

int binary_search(int a[], int low, int high, int target) { if (high < low) return -1; int middle = (low + high)/2; if (target  a[middle]) return binary_search(a, middle+1, high, target); else if (target == a[middle]) return middle; } 

Mi función tiene un prototipo específico (lo que significa que tiene un número determinado de argumentos que no se pueden modificar). Esto es lo que tengo hasta ahora.

 bool search(int value, int array[], int n) { if (array[n/2] == value) return 1; else if (array[n/2] < value) return search(value, &array[n/2], (n)/2); else // how do I "return" the other half? } 

¿Mi implementación parece correcta hasta ahora? Parece que no puedo encontrar la manera de implementar la statement final else .

Alto y bajo representan los límites del subarreglo en el que se continúa la investigación. Si analiza el código, notará que si el target es más pequeño que a[middle] , tendrá que continuar la investigación en la primera mitad de la matriz (de hecho, llama a binary_search pasando el mismo límite bajo pero, como superior enlazado, el middle real -1). En el otro lado, si el target es mayor que a[middle] , tendrá que continuar la investigación en la segunda mitad de la matriz (desde middle +1 hasta high ). Por supuesto, si el target es igual a a[middle] que has terminado.

El truco para escribir algo recursivo:

  1. Averigua cómo debería terminar.
  2. Averigua cómo debería verse un paso antes de que termine.
  3. Averigüe cómo debe verse dos pasos antes de que termine, y cómo pasar del # 2 al # 1 es exactamente lo mismo que pasar del # 3 al # 2.

Paso 1:

Si el número al principio del rango de búsqueda es el número deseado, devuelva verdadero.

Si el final del rango de búsqueda es el mismo que el comienzo del rango de búsqueda, y el número en el rango de búsqueda no es el número deseado, devuelva falso.

Paso 2:

Si el rango de búsqueda tiene una longitud de dos, divídalo en dos rangos de búsqueda de un elemento y busque el rango que pueda contener el número requerido.

Paso 3:

Si el rango de búsqueda tiene una longitud de más de dos, divídalo en dos rangos de búsqueda aproximadamente iguales, y busque el rango que pueda contener el número requerido.

(que combinando los dos parecería)

Si el rango de búsqueda tiene una longitud de dos o más elementos, divídalo en dos rangos aproximadamente iguales, marque el número más alto (último) en el rango “más bajo”, si el número es igual o menor que ese número, busque el número más bajo distancia; de lo contrario, busque en el rango superior.

Esta técnica no le devolverá una solución óptima a menos que seleccione una manera óptima de resolver el problema; sin embargo, te devolverá una solución correcta (siempre que no cometas errores verdaderos).

Ahora el codigo

 bool search(int value int array[], int lowIndex, int highIndex) { if (array[lowIndex] == value) { return true; } else if (lowIndex == highIndex) { return false; } int middleIndex = lowIndex + highIndex / 2; if (array[middleIndex] <= value) { return search(value, array, lowIndex, middleIndex); } else { return search(value, array, middleIndex+1, highIndex); } } 

Al leer el código en línea, tiene una gran desventaja. No realiza ninguno de los tres pasos anteriores, por lo que realmente tiene que resolver el problema al revés. Es como decir que tengo una solución, pero ahora tengo que descubrir cómo alguien más lo resolvió (asumiendo que no cometieron errores, y asumiendo que tenían exactamente los mismos requisitos que usted).

Las variables altas y bajas representan el rango actual que está buscando. Por lo general, comienza con el principio y el final de la matriz, y luego determina si el valor está en la primera o la segunda mitad, o exactamente en el medio. Si está en el medio, devuelve ese punto. Si está por debajo del medio, busca de nuevo (recursivamente), pero ahora solo en la mitad inferior. Si está por encima de la mitad, busca en la mitad superior. Y repite esto, cada vez dividiendo y reduciendo el rango. Si encuentra el valor, devuelve, de lo contrario, si el rango es tan estrecho que está vacío (los índices alto y bajo son iguales), no lo encontró.

Alto y bajo son los límites superior e inferior de los índices candidatos de la matriz. En otras palabras, definen la parte del subarreglo en la que es posible que exista el objective de búsqueda. Como el tamaño del subarreglo se reduce a la mitad de cada iteración, es fácil ver que el algoritmo es O (log n).

 return search(value, &array[(n)/2], (n)/2); 

En su código actual, en primer lugar, n no debe estar entre paréntesis (no hace una diferencia, pero me confunde).

A continuación, si está destinado a devolver el índice en la matriz, su código no lo hace, devuelve 1 . A juzgar por el prototipo, podría considerar un enfoque no recursivo, pero esto puede funcionar bien si agrega los valores correctos a cada devolución.

Puedes averiguar la otra afirmación. Simplemente haga un dibujo, averigüe dónde deberían estar los punteros y codifíquelos. Aquí hay un comienzo:

  new array if > n/2 v-----------v 0, 1, 2, 3, 4, 5, 6, 7 ^ n/2 

En realidad, probablemente no quieras incluir tu valor medio. Finalmente, asegúrese de tomar en cuenta las listas de longitud cero, uno, dos y tres. Y por favor escriba pruebas unitarias. Este es probablemente uno de los algoritmos implementados de manera más incorrecta.

He intentado resolver su problema y este código de abajo realmente funciona. Pero, ¿cuál es la condición para escapar de la recursión si el valor que se desea buscar no está en la matriz?

 if(value==a[size/2]) return size/2; if( valuea[size/2] && a[size/2] 
 int * binSearch (int *arr,int size, int num2Search) { if(size==1) return ((*arr==num2Search)?(arr):(NULL)); if(*(arr+(size/2))