Me han pedido hacer el algoritmo de búsqueda dicotómica o búsqueda binarias.
El caso es que lo tengo hecho per el problema es que no acaba de funcionar correctamente.
Aquí os dejo el algoritmo a ver si me podéis decir por qué intente buscar el número que intente siempre me dice que está en la posición 0.
PD: Solo es el case7
y la "función 7". He decidido pasar todo el programa porque creo que así se entiende mejor.
Código:
#include <stdio.h>
#include <stdlib.h>
#define nmax 50
void llegir_vector (int vector [],int num);
void mostrar_vector (int vector [], int num);
int buscar_vector (int vector [], int num, int num_buscar);
int repeticions (int vector [], int num, int num_element);
int posicio_maxima (int vector [], int num);
void bombolla (int vect [], int num);
void dicotomica (int vector [], int num);
void main () {
int cont, n, num, i, opcion, res, num_buscar, num_element;
int vector[nmax];
n = 1;
while (n!=0) {
printf ("\nSelecciona una opcio: \n");
printf ("---------------------\n");
printf ("1.- Introduïr un vector:\n");
printf ("2.- Mostra el vector per pantalla.\n");
printf ("3.- Buscar un element en el vector.\n");
printf ("4.- Comptar quantes vegades apareix el mateix caràcter en el vector.\n");
printf ("5.- Buscar la posició de l'element més gran del vector.\n");
printf ("6.- Ordena el vector amb el métode de la bombolla.\n");
printf ("7.- Busca un element en el vector mitjançant la búsqueda dicotòmica.\n");
printf ("0.- Sortir del programa.\n");
printf ("------------------------\n");
scanf ("%d", &n);
switch (n) {
case 1:
system("clear");
printf("Introdueix la longitud del vector: ");
scanf ("%d", &num);
printf ("Introdueix el vector: ");
llegir_vector (vector, num);
break;
case 2:
system("clear");
mostrar_vector (vector, num);
break;
case 3:
system("clear");
printf ("Escriu el número a buscar: ");
scanf ("%d", &num_buscar);
res = buscar_vector(vector, num, num_buscar);
if (res == -1){
printf ("No s'ha trobat cap.\n");
}
else {
printf ("És la posició: %d\n", res);
}
break;
case 4:
system("clear");
printf ("Escriu el número que vols comptar les vegades que es repeteix: ");
scanf ("%d", &num_element);
res = repeticions(vector, num, num_element);
printf ("El %d es repeteix %d vegades.\n", num_element, res);
break;
case 5:
system("clear");
res = posicio_maxima(vector, num);
printf ("La posició del element màxim es la posició %d.\n", res);
break;
case 6:
system("clear");
bombolla (vector, num);
printf ("Vector ordenat!!!!!\n");
break;
case 7:
system("clear");
printf ("Escriu el número a buscar: ");
scanf ("%d", &num_buscar);
dicotomica (vector, num);
if (res == -1){
printf ("No s'ha trobat cap.\n");
}
else {
printf ("Si s'ha trobat, està en la posició: %d\n", res);
}
break;
}
}
}
// Función número 1.
void llegir_vector (int vector [],int num) {
int i;
for (i = 0; i<num; i++) {
scanf("%d", &vector[i]);
}
}
// Función número 2.
void mostrar_vector (int vector [],int num) {
int i;
for (i = 0; i<num; i++) {
printf ("%d ", vector[i]);
}
}
// Función número 3.
int buscar_vector (int vector [], int num, int num_buscar) {
int i, cont;
i = 0;
while (i < num){
if (vector[i] == num_buscar){
return (i);
}
i ++;
}
return (- 1);
}
// Función número 4.
int repeticions (int vector [], int num, int num_element) {
int i, cont_repeticiones;
i = 0;
cont_repeticiones = 0;
while (i < num){
if (vector[i] == num_element){
cont_repeticiones ++;
}
i ++;
}
return (cont_repeticiones);
}
// Función número 5.
int posicio_maxima (int vector [], int num) {
int i, max;
i = 0;
max = 0;
while (i < num){
if (vector[i] > max){
max = vector[i];
}
i ++;
}
return (max);
}
//Funciçon número 6.
void bombolla (int vector [], int num) {
int i, j, canvi, aux;
canvi = 1;
i = 0;
aux = 0;
while ( canvi == 1){
canvi = 0;
for (j = 0; j <=num-i-2; j++){
if (vector[j] > vector[j+1]){
aux = vector[j];
vector[j] = vector[j+1];
vector[j+1] = aux;
canvi = 1;
}
}
i ++;
}
}
//Función número 7.
void dicotomica (int vector [], int num) {
int i, izq, der, centro, valor;
i = 0;
izq = 0;
der = num - 1;
while ((vector[centro] != valor) && (izq < der)) {
centro = (izq + der) / 2;
if (vector [centro] < valor) {
izq = centro + 1 ;
}
else {
der = centro - 1;
}
centro = (izq + der) / 2;
}
if (valor == vector [centro]) {
return (i);
}
else {
return (- 1);
}
}
dicotomica()
retorna el valor dei
, el cual incializas con cero y luego ya no cambia más en todo el bucle. Creo que lo que deberías retornar es el valor decentro
, si no lo he entendido mal.