Para encontrar algo dentro de una estructura de datos los algoritmos más conocidos son la búsqueda lineal y binaria. Los dos métodos de búsqueda que se explican en este capítulo, se usarán con los mismos arreglos dinámicos antes vistos: LNaturales, LEnteros, LReales y LPalabras.
La búsqueda lineal también se conoce como búsqueda secuencial. El algoritmo de la búsqueda lineal es muy simple y consiste en ir comparando cada uno de los elementos de la lista, hasta encontrar el elemento buscado, a continuación un programa de ejemplo:
La función BusquedaLineal devuelve verdadero cuando encuentra lo que se buscaba, y la posición lo devuelve en el parámetro pos, cuando no encuentra nada devuelve el valor falso y en pos se devuelve la posición del último elemento de la lista. Este algoritmo funcionará sin importar si la lista esta ordenada o desordenada.
La búsqueda binaria sólo se usa con listas ordenadas, tanto en orden ascendente como en orden descendente, este algoritmo es recomendado para listas de regular tamaño, la idea consiste en tomar el elemento central de la lista, si el elemento central es mayor que el que se está buscando, entonces el valor puede estar en la parte izquierda o superior de la lista, y se busca en esa parte tomando un nuevo elemento central y así sucesivamente, lo mismo se hace para la parte derecha o inferior hasta encontrar el número. Ejemplo:
La función busquedabinaria usa las siguientes variables, primero, ultimo, mitad y una variable de tipo boolean encontro. Las variables ultimo y primero siempre tendrá los índices o posiciones de donde empiezan y terminan las partes en que se va dividiendo la búsqueda.
Al momento de ingresar al bucle while se toma la mitad del arreglo que será la suma del primero con el ultimo y dividido con 2, tomando sólo la parte entera. Una vez obtenido la posición media o la mitad se compara el elemento que se encuentra en esa posición, y si es igual entonces se sale del bucle haciendo que la variable encontro tome el valor true. En caso no sea igual se verifica si el elemento de la posición media o mitad es mayor que el valor buscado, que en este caso es el valor de la variable k. Si es mayor entonces a ultimo se le asigna la mitad menos 1, para seguir buscando en la parte superior o izquierda del arreglo, en caso contrario a primero se le asigna la mitad más 1, para segur buscando en la parte inferior o derecha del arreglo.
Debido a que primero y ultimo se irán acercando, conforme se realice la búsqueda o se vaya recorriendo el arreglo, el bucle while debe verificar si ultimo es mayor que primero, si ultimo es mayor que primero entonces se sigue con la busqueda, en caso contrario se termina el bucle. En caso se haya encontrado el valor buscado la variable mitad tendrá la posición en donde se encontró y la variable encontro tendrá el valor true.
Al comparar la variable ultimo con la variable primero, se hace un solapamiento de la variable ultimo con el tipo de dato longint, esto es debido a que si buscamos un valor menor que no se encuentre al inicio del arreglo, mitad tendría un cero que al restarle un 1 nos dará el valor más alto del tipo de dato longword, y el bucle continuaría. Al solapar el valor de ultimo con el tipo de dato longint, haremos que el valor más alto que tenga ultimo se convierta en un número negativo permitiendo de ese modo terminar el bucle.
En caso queramos hacer una búsqueda de un elemento en un lista ordenada en orden descendente, entonces se tiene que hacer un cambio en el algoritmo, este cambio sólo se hace al comparar el elemento medio con el elemento a buscar. En ves de usar el operador > se debe usar el operador <.