Tipos de algoritmos de búsqueda

Los algoritmos de búsqueda forman una parte importante de muchos programas. Algunas búsquedas implican buscar una entrada en una base de datos, como buscar su registro en la base de datos del IRS. Otros algoritmos de búsqueda se arrastran a través de un espacio virtual, como los que buscan los mejores movimientos de ajedrez. Aunque los programadores pueden elegir entre numerosos tipos de búsqueda, seleccionan el algoritmo que mejor se adapta al tamaño y la estructura de la base de datos para brindar una experiencia fácil de usar.

La búsqueda lineal es el algoritmo de elección para las listas cortas, porque es simple y requiere un código mínimo para implementar. El algoritmo de búsqueda lineal examina el primer elemento de la lista para ver si lo está buscando y, si es así, ha terminado. De lo contrario, examina el siguiente elemento y recorre cada entrada de la lista.

La búsqueda binaria es un algoritmo popular para grandes bases de datos con registros ordenados por clave numérica. Los candidatos de ejemplo incluyen la base de datos del IRS codificada por número de seguro social y los registros del DMV codificados por números de licencia de conducir. El algoritmo comienza en el medio de la base de datos: si su número objetivo es mayor que el número del medio, la búsqueda continuará con la mitad superior de la base de datos. Si su número objetivo es menor que el número del medio, la búsqueda continuará con la mitad inferior de la base de datos. Sigue repitiendo este proceso, cortando la base de datos a la mitad cada vez hasta que encuentra el registro. Esta búsqueda es más complicada que la búsqueda lineal, pero para bases de datos grandes es mucho más rápida que una búsqueda lineal.

Una búsqueda de árbol solo funciona si los datos encajan en una estructura de árbol. La base de datos comienza en una raíz que va a algunos elementos, cada uno de los cuales va a algunos elementos más y así sucesivamente hasta que tenga un árbol. Un ejemplo es el juego de ajedrez. La posición actual de la placa es la raíz. Los movimientos legales desde esta posición representan un paso hacia abajo en el árbol, y así sucesivamente hasta que el jugador encuentra la posición del tablero que lo deja en la mejor posición.

La búsqueda de un algoritmo genético es una de las técnicas detrás de la inteligencia artificial. Busca una "solución óptima" expresada como una cadena de datos, como la lista de dimensiones internas de un motor a reacción que proporciona el máximo empuje. La búsqueda comienza con una población aleatoria de cadenas y prueba cada una, conservando las mejores y criándolas para obtener la próxima generación. El programa sigue repitiendo este proceso hasta que llega a una cadena de solución óptima.