Algoritmos de búsqueda

Un algoritmo de búsqueda sirve para localizar un elemento concreto dentro de una estructura de datos. Consiste en averiguar si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste.

Este problema puede reducirse a devolver la existencia de un número en un vector.
Básicamente existen 2 algoritmos para resolver el problema.



Búsqueda secuencial
Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del vector hasta que éste se encuentre, o hasta que se llegue al final del vector. La existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo.

vector=['1','33','23','45','12','78','99','21','31']
valor_a_buscar='21'

posicion=0
encontrado='No'
posicion_del_valor_a_buscar=0
longuitud_del_vector=len(vector)

while posicion< longuitud_del_vector:
 if vector[posicion]==valor_a_buscar :
  posicion_del_valor_a_buscar=posicion
  encontrado='Si'
 posicion=posicion+1

if encontrado=='Si':
 print 'Valor '+valor_a_buscar+' encontrado en posicion '+str(posicion)
else:
 print 'Valor no encontrado'

Búsqueda dicotómica
Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado.Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones. Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del vector (normalmente el elemento central), si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del vector que va desde el inicio de éste hasta el elemento tomado.En caso contrario se toma la parte del vector que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el vector.

# coding=utf-8

#Datos de Entrada:
vector=['2','12','19','31','36','44','45','59','61','99']
  # vector en el que se desea buscar el elemento
tam=len(vector) 
  # tamaño del vector
dato='44'
  # elemento que se quiere buscar.

#Variables
centro=0 #elemento central del intervalo
inf=0 #limite inferior del intervalo
sup=0 #limite superior del intervalo
encontrado='No' #indica si se encuentra el dato
posicion=0 #posicion del elemento encontrado

inf = 0
sup = tam-1

while inf <= sup:
 centro = ((sup + inf) / 2) 
 if vector[centro] == dato:
  encontrado='Si'
  posicion=inf
 if dato < vector[centro]:
  sup=centro-1
 else:
  inf=centro+1

if encontrado=='Si':
 print 'Valor '+dato+' encontrado en posicion '+str(posicion)
else:
 print 'Valor no encontrado'