Presentación

           

Universidad de Panamá

Centro Regional Universitario de Coclé

Programación II

Parcial 2

Algoritmo de Búsqueda

Profesora: Dayalis Vargas

Estudiante: Marichell Araúz

Cédula: 2-749-655

Fecha: 23/06/21

Título

 

ALGORITMO DE

 BÚSQUEDA

Introducción

INTRODUCCIÓN

Conceptos de Algoritmo de Búsqueda

DEFINICIÓN 

Un algoritmo de búsqueda es un conjunto de instrucciones que están diseñadas para localizar un elemento con ciertas propiedades dentro de una estructura de datos.

FUNCIÓN

Los procesos de búsqueda involucran recorrer un arreglo completo con el fin de encontrar algo. Lo más común es buscar el menor o mayor elemento (cuando es puede establecer un orden), o buscar el índice de un elemento determinado.

Para buscar el menor o mayor elemento de un arreglo, podemos usar la estrategia, de suponer que el primero o el último es el menor (mayor), para luego ir comparando con cada uno de los elementos, e ir actualizando el menor (mayor). A esto se le llama Búsqueda Lineal.

Para encontrar un dato dentro de un arreglo, para ello existen diversos algoritmos que varían en complejidad, eficiencia, tamaño del dominio de búsqueda.

Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste.

TIPOS

Existen diferentes algoritmos de búsqueda y la elección depende de la forma en que se encuentren organizados los datos: si se encuentran ordenados o si se ignora su disposición o se sabe que están al azar. También depende de si los datos a ordenar pueden ser accedidos de modo aleatorio o deben ser accedidos de modo secuencial.

Búsqueda Secuencial

BÚSQUEDA SECUENCIAL

Es un método para encontrar un valor objetivo dentro de una lista. Ésta comprueba secuencialmente cada elemento de la lista para el valor objetivo hasta que es encontrado o hasta que todos los elementos hayan sido comparados.

FUNCIÓN

Este método consiste en recorrer el arreglo o vector elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del vector y se observa una casilla tras otra hasta que se encuentre el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el vector o arreglo no esta en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya se en el primer elemento, como en el ultimo. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del vector.

Ventajas y Desventajas de Búsqueda Secuencial

 Ventajas

• Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeños (Hasta aproximadamente 500 elementos).

• Es fácil adaptar la búsqueda secuencial para que utilice una lista enlazada ordenada, lo que hace la búsqueda más eficaz.

• Si los datos buscados no están en orden es el único método que puede emplearse para hacer dichas búsquedas.

Desventajas

• Este método tiende hacer muy lento.

• Si los valores de la clave no son únicos, para encontrar todos los elementos con una clave particular, se requiere buscar en todo el arreglo, lo que hace el proceso muy largo.

Algoritmo de Búsqueda Secuencial

 //Busqueda Secuencial

#include<iostream>

#include<conio.h>

using namespace std;

int main(){

int a[] = {3,4,2,1,5};

int i,dato;

char band = 'F';

dato = 2; 

i=0;

while((band == 'F') && (i<5)){

if(a[i] == dato){

band = 'V';

}

i++;

}

if(band == 'F'){

cout<<"El numero a buscar no existe en el arreglo"<<endl;

}

else if(band == 'V'){

cout<<"El numero a sido encontrado en la posicion: "<<i-1<<endl;

}

getch();

return 0;

}

Video de Algoritmo de Búsqueda Secuencial

 

Algoritmo de búsqueda Secuencial

Búsqueda Binaria

BÚSQUEDA BINARIA

DEFINIR

Es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos. Funciona al dividir repetidamente a la mitad la porción de la lista que podría contener al elemento, hasta reducir las ubicaciones posibles a solo una. La búsqueda binaria es el método, donde si el arreglo o vector esta bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

FUNCIÓN

El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central. Este método se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda.

Ventajas y Desventajas de Búsqueda Binaria

 

Ventajas

• Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda.   

• Es el método más eficiente para encontrar elementos en un arreglo ordenado.

Desventajas

• Este método funciona solamente con arreglos ordenados, por lo cual si nos encontramos con arreglos que no están en orden, este método, no nos ayudaría en nada.

Algoritmo de Búsqueda Binaria

//Busqueda Binaria

#include<iostream>

#include<conio.h>

using namespace std;

int main(){

int numeros[] = {1,2,3,4,5};

int inf,sup,mitad,dato,i;

char band='F';

dato = 1;

inf=0;

sup=5;

i=0;

while((inf<=sup)&&(i<5)){

mitad = (inf+sup)/2;

if(numeros[mitad] == dato){

band='V';

break;

}

if(numeros[mitad]>dato){

sup = mitad;

mitad = (inf+sup)/2;

}

if(numeros[mitad]<dato){

inf = mitad;

mitad = (inf+sup)/2;

}

i++;

}

if(band == 'V'){

cout<<"El numero se encontro en la posicion: "<<mitad<<endl;

}

else{

cout<<"El numero NO se encontro";

}

getch();

return 0;

}