Diario de un programador.- Día 176
Búsqueda
lineal en C
Cuando se
trabaja con grandes cantidades de datos, por ejemplo con arreglos. Se puede dar
la ocasión de que sea necesario buscar algún elemento en específico para saber
si existe o no en nuestro arreglo. Este proceso se conoce como
"búsqueda". Se estudiarán dos métodos de búsqueda: La técnica simple
de búsqueda lineal y otra técnica más
eficiente conocida como búsqueda binaria.
La
búsqueda lineal consiste en comparar cada uno de los elementos del arreglo con
el valor buscado, así que la velocidad de búsqueda dependerá en que parte del
arreglo se encuentre lo que se busca, ya que el valor buscado puede estar al
principio del arreglo como al final de este. Por lo tanto, en promedio, el
programa tendrá que comparar el valor buscado con la mitad de los elementos del
arreglo.
El
arreglo lineal funciona bien para arreglos pequeños o que no están ordenados. Si el arreglo está ordenado, se puede utilizar
la técnica de búsqueda binaria, la cual es mucho más eficiente con arreglos
ordenados.
Entonces,
como se dijo anteriormente, la búsqueda lineal compara uno a uno los elementos
del arreglo con el valor buscado. Ejemplo:
Si
quisiera buscar el elemento 80 en el arreglo, entonces lo que se hará es comparar
ese valor uno a uno, desde el principio hasta hallarlo.
Un
ejemplo sencillo de esto sería lo siguiente, suponiendo que el arreglo ya tiene
asignado los elementos:
A partir de ese pequeño
código que puse, fui implementando el programa poco a poco hasta completarlo.
#include<stdio.h>
int main(void){
int lista[51];
int i;
//llenamos la lista
for(i =
0; i <= 50; i++){
lista[i] = i * 2; //números pares
} //fin for
//mostramos la lista
for(i = 0; i <= 50; i++){
printf("%d ",lista[i]);
if(i % 10 == 0 && i != 0) //Para
realizar un salto cada 10 elementos
printf("\n");
}
return 0;
} //fin main
Esta primera parte lo que
hace es crear un arreglo el cual es rellenado con números pares y luego es
mostrado por pantalla.
Lo
siguiente que se hará, será solicitar al usuario que ingrese un número. Ese
número será guardado en una variable y será comparado con cada uno de los
elementos del arreglo. Además se utilizará una variable auxiliar llamada
"buscador" que cambiará su valor dependiendo si el elemento fue
encontrado o no. El valor final de esta variable servirá para mostrar un
mensaje al usuario.
//solicitamos un numero
printf("\nQue numero buscaras: ");
scanf("%d", &numero);
for(i = 0;
i <= 50; i++){
if(lista[i]
== numero){
printf("Numero encontrado\n") ;
buscador = i; //Si el numero es encontrado, se
modifica esta variable
break; //Salimos del
ciclo
}
else{
buscador = -1; //Si no se encuentra, esta
variable tendrá este valor
}
} //fin for
if
(buscador == -1){
printf("Numero no encontrado\n");
}
Ahora que
se sabe que existe un elemento en el arreglo, sería interesante saber en qué
lugar específicamente se encuentra ese elemento, ya que podríamos tener un arreglo
muy grande y en ocasiones nos gustaría saber el lugar exacto donde se
encuentra. Para eso, se le añadirá una condición else. Además se modificará el
lugar de ubicación del mensaje cuando el elemento es encontrado. Este se
ubicará ahora dentro de la instrucción else.
else{
printf("Numero
encontrado en posicion [%d]\n", buscador);
}
Ahora,
con esta instrucción agregada, probaremos nuevamente el programa y se verá que
ahora indica en qué posición fue encontrado el elemento.
Ahora sí que se podría decir que el programa está
listo.
El código completo es el siguiente:
#include<stdio.h>
int main(void){
int numero;
int lista[51];
int i;
int buscador;
//llenamos la lista
for(i =
0; i <= 50; i++){
lista[i] = i * 2;//numeros pares
}//fin
for
//mostramos la lista
for(i = 0; i <= 50; i++){
printf("%d ",lista[i]);
if(i % 10 == 0 && i != 0)
printf("\n");
}
//solicitamos un numero
printf("\nQue numero buscaras: ");
scanf("%d", &numero);
for(i = 0; i <= 50; i++){
if(lista[i] == numero){
buscador = i;
break;
}
else{
buscador = -1;
}
}//fin
for
if (buscador == -1){
printf("Numero no encontrado\n");
}
else{
printf("Numero encontrado en posicion [%d]\n", buscador);
}
return 0;
}//fin main
Antes de
dar por terminado este capítulo un pequeño desafío. ¿Cómo escribirían un
programa que realice una búsqueda lineal utilizando funciones? La gracia está
en que la función sea capaz de recibir el arreglo como parámetro.
Aquí está
mi solución.
#include <stdio.h>
void funcion(int[], int, int);
void funcion(int arreglo[], int tam, int busca){
int i,
contador = 0;
for(i = 0; i
< 10; i++){
if(arreglo[i]
== busca){
printf("Numero encontrado en indice
%d\n", i);
break;//para que no siga buscando si ya
lo encontro
}
else{
contador++;//por cada busqueda sin exito
suma 1 a contador
}
}//fin for
if (contador == 10)
printf("Numero no encontrado\n");
}//fin funcion
int main(void){
int num, x, arreglo[10];
printf("Ingresa un numero: ");
scanf("%d", &num);
printf("LISTA DE NUMEROS\n");
for(x = 0; x < 10; x++){
arreglo[x] = x * 2;
printf("%d ",arreglo[x]);
}
printf("\n\n");
funcion(arreglo,10, num);
return 0;
}
En el
próximo capítulo de programación en C, se analizará la búsqueda binaria. Hasta
entonces.
Gustavo J. Cerda Nilo
Junio 2016, Octubre 2016
cómo sería para probar el programa llena el arreglo con n ́umeros aleatorios usando la función rand().
ResponderEliminarno c
ResponderEliminar