Búsqueda dicotómica de un elemento en una matriz ordenada

No aprendimos C en el mismo lugar. ¿Intentaste compilar tu código?

¿De dónde tomaste este código?

En la función view, ¿por qué cambias el valor de inf y sup?

Con un poco de imaginación, podría parecer una búsqueda dicotómica.

Hay varias implementaciones iterativas de este algoritmo.

Haz una búsqueda en la web.

P.S. Una búsqueda dicotómica se realiza sobre un arreglo ordenado (este es el caso aquí)

Quizá antes de lanzarte a este ejercicio deberías corregir (entender) éste https://forums.commentcamarche.net/forum/affich-38004912-exercice-sur-les-pointeurs#dernier

Cuando era niño, el mar Muerto estaba simplemente enfermo.
George Burns

Varios errores por tan poco código:
No es la forma correcta de declarar un enum ni un typedef.
Existe el tipo bool en <stdbool.h>
Las definiciones de enum y de tablas se hacen con { } en lugar de ( )
Estás usando *elt mientras que elt no ha sido definido como puntero (ver el enlace de Whismeril).
En view(), el bucle va de 5 a 32 en lugar de infinito de abajo hacia arriba. Me hace creer que hay una incomprensión de pasar los parámetros.

No mostrarás lo que crees mostrar.

En fun(), las llamadas recursivas no devuelven nada.
Y el algoritmo en sí no es correcto.

edición: funciona pero obliga a descender a un intervalo de un solo elemento.

Hola,

Comentarios preliminares

Gracias por compartir en el futuro tus fragmentos de código como se explica aquí y sobre todo por indentar correctamente, eso evitará errores de programación. También te recomiendo abrir y cerrar sistemáticamente pares de llaves después de cada if/else/for/while y volver a la línea después de cada { y cada }, eso hará que tu código sea más legible y probablemente evitará errores de programación en proyectos más largos.

A continuación, también sería buena idea usar un título de discusión menos vago y explicar el objetivo de tu programa.

Comentarios sobre el código

La línea 3 está mal escrita:

• como señaló Pierrot #3, el tipo bool se usa así:

#include <stdbool.h> int main() { bool b1 = true; bool b2 = true; return 0; } 

La línea 14 es "confusante" porque si entiendo bien tu programa, inf debe ser siempre menor o igual que sup y por tanto yo habría distinguido más bien:

if (inf < sup) { // Seguir estrechando [inf, sup] } else if (inf == sup) { // Ver si el elemento está justo aquí } else { // Error, no deberíamos estar en este caso }

La línea 15 me parece muy sospechosa.

• Si quieres hacer una prueba (lo que a mi juicio es el fallo que buscas y que te trae aquí, por cierto), debes escribir :

if (vec[med] == *elt)

• Actualmente, estás haciendo una asignación de *elt en vec[med]. El resultado de esta operación es el valor asignado en vec[med]. Si este valor es distinto de cero entonces la prueba es verdadera, de lo contrario es falsa. Esto significa que cada vez que haces esta prueba, modificas el contenido de vec. Dudo que eso sea lo que quisieras escribir. Como escribir = en lugar de == es fácil de cometer, normalmente tu compilador te avisa. En los casos en que realmente quieras hacer la prueba + la asignación, el compilador esperará que insistas duplicando los paréntesis del if. En tu caso, esto volvería a escribirse como:

if ((vec[med] = *elt))

Cómo mostrar una parte de un arreglo

Voy a reformularlo con mayor precisión: cómo mostrar una porción (slice) del arreglo tab de tipo int *, desde el índice i (incluido) hasta el índice j (excluido).

#include <stdio.h> void print_tab( int * tab, size_t num_elements, size_t i, size_t j ) {     printf("[");     for (size_t k = i; k < j; k++) {         printf(" %d", tab[k]);     }         printf(" ]\n"); }      int main() {     int tab[] = {10, 20, 30, 40, 50, 60};     size_t num_elements = sizeof(tab) / sizeof(int);     print_tab(tab, num_elements, 0, 6); // [ 10 20 30 40 50 60 ]     print_tab(tab, num_elements, 2, 5); // [ 30 40 50 ]     print_tab(tab, num_elements, 2, 3); // [ 30 ]     print_tab(tab, num_elements, 2, 2); // [ ]     print_tab(tab, num_elements, 2, 1); // [ ]     return 0;       } 

Version itérative

En líneas generales, hay que reemplazar tu llamada recursiva y usar un bucle while del que deberás salir cuando se alcance un criterio de parada.

La primera cosa a hacer es entender cuáles son esos criterios de parada, y cómo garantizar que en cada iteración del bucle, reduces estrictamente tu espacio de búsqueda.

Como aquí tu objetivo es estrechar tus índices inf y sup para encontrar med, así que hay buenas probabilidades de que tu criterio de parada consista en verificar si inf == sup y asegurarte de que en cada iteración, ya sea inf se acerque a sup, o sup se acerque a inf.

Bonne chance

@mamiemando, me pregunto si Steve17_17 ha entendido cómo calcular la longitud de un arreglo con la fórmula:
    num_elements = sizeof(tab) / sizeof(tab[0]);
Esta variable no se usa en la función print_tab().
Supongo que le dejaste a él la tarea de calcularlo por sí mismo si los límites i y j eran correctos.
Matemáticamente: 0 <= i < j <= num_elements
Una cosa que puede molestar al principiante que busca una implementación es el hecho de que hay dos variantes posibles:
En primer lugar, inf es el índice del primer elemento y sup es el índice del último.
En segundo lugar, inf es siempre el índice del primero, pero sup es el índice del siguiente al último.
En esta segunda variante, sup - inf es la longitud del subarreglo a buscar.
La prueba de estrechamiento y ajuste de inf o sup respecto a med es ligeramente diferente.
La idea de estrechar alrededor del elemento buscado es correcta pero no necesariamente la más eficiente.
Doy un ejemplo simple con el siguiente arreglo:
[10, 20, 30, 40, 50, 60, 70]
con la segunda variante, inf = 0 y sup = 7 y busco el valor 40.
Entonces, med = (inf + sup) / 2 = (0 + 7) / 2 = 3
Y precisamente 40 está en el índice 3. Lo encuentro en la primera recursión (o iteración)
La idea es probar los límites y evaluar el valor de med inmediatamente después.
Si inf > sup o inf >= sup según la variante, no se encontró.
De lo contrario, se calcula de inmediato el valor de med y se prueba si el valor en esa posición es el buscado.
Si es así, se sale con true o el índice donde se encuentra el valor buscado.
De lo contrario, se busca en lo que precede o lo que sigue según si este valor viene antes o después del de la posición med.
Primera variante: fun(tab, inf, med-1) o fun(tab, med+1, sup)
Segunda variante: fun(tab, inf, med) o fun(tab, med+1, sup)

De acuerdo, muchas gracias, he tomado nota.