Algoritmos de Búsqueda.

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

BUSQUEDA BINARIA

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado. Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

Código Python

def busqueda_binaria(lista, x):
    Precondición: lista está ordenada

    Devuelve -1 si x no está en lista;

    Devuelve p tal que lista[p] == x, si x está en lista

   

    # Busca en toda la lista dividiéndola en segmentos y considerando

    # a la lista completa como el segmento que empieza en 0 y termina

    # en len(lista) - 1.

    izq = 0 # izq guarda el índice inicio del segmento

    der = len(lista) -1 # der guarda el índice fin del segmento

    # un segmento es vacío cuando izq > der:

    while izq <= der:

        # el punto medio del segmento

        medio = (izq+der)/2

        print "DEBUG:", "izq:", izq, "der:", der, "medio:", medio

        # si el medio es igual al valor buscado, lo devuelve

        if lista[medio] == x:

            return medio

        # si el valor del punto medio es mayor que x, sigue buscando

        # en el segmento de la izquierda: [izq, medio-1], descartando la

        # derecha

        elif lista[medio] > x:

            der = medio-1

        # sino, sigue buscando en el segmento de la derecha:

        # [medio+1, der], descartando la izquierda

        else:

            izq = medio+1

        # si no salió del ciclo, vuelve a iterar con el nuevo segmento

    # salió del ciclo de manera no exitosa: el valor no fue encontrado

    return -1

# Código para probar la búsqueda binaria

def main():

    lista = input ("Dame una lista ordenada ([[]] para terminar): ")

    while lista != [[]]:

        x = input("¿Valor buscado?: ")

        resultado = busqueda_binaria(lista, x)

        print "Resultado:", resultado

        lista = input ("Dame una lista ordenada ([[]] para terminar): ")

BÚSQUEDA SECUENCIAL

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Código Python

def sequentialSearch(alist, item):
   pos = 0
   found = "El valor no está en la lista"

   while pos < len(alist) and not found:
       if alist[pos] == item:
           found = "Se encontró el valor!"
       else:
           pos = pos+1

   return found



lista=[]
cn=int(raw_input("Cantidad de numeros a ingresar: "))

for i in range(0,cn):
    lista.append(int(raw_input("Ingrese numero %d : " % i)))


n=int(raw_input("Dame el numero a buscar:  "))

print(sequentialSearch(lista, n))

Referencias

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheSequentialSearch.html http://macabremoon0.tripod.com/id2.html
https://ronnyml.wordpress.com/2009/07/09/busqueda-lineal-y-busqueda-binaria/
http://librosweb.es/libro/algoritmos_python/capitulo_8/busqueda_binaria.html