Algoritmos de busqueda secuencial y binaria

INTRODUCCION
La búsqueda es una operación que tiene como objeto la localización de un elemento dentro de la estructura de datos con la que estamos trabajando.
Un algoritmo de búsqueda es una técnica para encontrar un valor dentro de la estructura, determinado como campo clave o llave.
La búsqueda termina.- con éxito, si encuentra la llave dentro de la estructura, sin éxito, pues no encuentra la llave dentro de la estructura.
El método de búsqueda a aplicar depende de si la lista esta ordenada o desordenada.
En base a esto, los algoritmos de búsqueda se clasifican en:

• Internos.- aquellos que aplican a estructuras de datos como arreglos, tablas, listas ,etc.
• Externos.- aquellos que aplican a archivos que se encuentran en dispositivos electrónicos.

También se pueden clasificar de acuerdo a si los datos se encuentran en orden o desordenados:

• Secuencial o Lineal
• Binaria o directa

BUSQUEDA SECUENCIAL
Es la forma mas simple de los métodos de búsqueda.
Consiste en reconocer y examinar cada uno de los elementos de la Lista o Arreglo, hasta encontrar el o los elementos buscados, o hasta haber recorrido todos los elementos de la lista.
Se define como el proceso de determinar el elemento, o su posición, que cumple con una condición; comparando con cada uno de los elementos en forma secuencial.
Se recomienda utilizar cuando el arreglo o lista no esta ordenado.

 

CODIFICACION EN C++:

1 int busq_lineal(int N, int array[],int elemento)

2 {    

3      int i,j;

4      for(i=j=0;i<N;i++)
5      {    
6           if(array[i]==elemento)
7           {    
8               return(i)

9           }

10     }

11     return(-1)

12 }

BUSQUEDA BINARIA
Es el método mas eficiente de búsqueda en una lista ordenada.
Básicamente el valor se compara con el elemento intermedio de la lista.
Sin son iguales, la búsqueda termina exitosamente; en caso contrario, debe buscarse en la mitad superior o inferior de la lista, repitiendo el proceso anterior.
Si recorre la lista y no ubica el valor, entonces no tiene éxito.

CODIFICACION EN C++:

1 int busqbin(int n,int a[],int valor)
2 {
3    int izq=1,der=n-1,medio;   
4    while(izq<=der)
5    {
6         medio=(izq+der)/2;
7         if(valor==a[medio])
8         {
9               return(medio);
10        }
11        if(valor>a[medio])
12        {
13                   izq=medio+1;
14        }
15        else
16        {
17            der=medio-1;
18        }
19   }
20   return(-1);
21 }
 

Fuente:
http://ronnyml.wordpress.com/2009/07/09/busqueda-lineal-y-busqueda-binaria/
http://www.algoritmia.net/articles.php?id=32