Búsqueda de datos

Trabajar problemas de búsqueda implica verificar la existencia de un elemento o un valor en el vector o lista seleccionada. Encontrar dicho elemento consiste en poder bifurcar por la rama afirmativa de una decisión, al mismo tiempo que podremos dar la ubicación del elemento buscado, mismo que puede ser un índice, un apuntador o cualquier otro referente del valor hallado.

Si el arreglo contiene valores múltiples (esto es, valores con repetición), el problema de búsqueda exige indicar: un único elemento, definido por convención, ya sea el índice menor, el mayor o bien todas las posiciones.

Los métodos de búsqueda que estudiaremos son:

· Búsqueda secuencial, y

· Búsqueda binaria.

Búsqueda secuencial

Si tenemos una lista de elementos almacenados en un vector. El método más simple de búsqueda de un elemento en dicho vector consiste en recorrer uno a uno el vector desde el inicio hasta el último elemento, hasta encontrar o los elementos buscados, generando un mensaje o bien alertando con una variable bandera o centinela el resultado de esa operación.

La búsqueda secuencial compara cada elemento del vector con el valor buscado, hasta que éste se encuentra o se termina de leer el vector completo.

Algoritmo

Constante TAM 20

inicio

entero v[TAM], i, num, cont = 0;

Genera aleatorios

escriba("Llenar arreglo con números aleatorios del 0 al 50")

para(i = 0; i < TAM; i++)

v[i] = aleatorio() % 50

fin-para

escriba("Arreglo generado:")

para(i = 0; i < TAM; i++)

escriba(v[i])

escriba("Número a buscar ")

leer(num)

para(i = 0; i < TAM; i++)

si(v[i] == num)

entonces

cont = cont + 1

if(cont == 1)

escriba("Valor encontrado")

fin-si

escriba("Posicion: ", i)

fin-para

si(cont == 0)

entonces

escriba("El valor ", num, no existe")

fin-si

Código C++

Búsqueda binaria

Para listas o arreglos de datos ordenados, el método de búsqueda binaria funciona de manera ó, considerándose el más eficaz. Está sustentado en la lógica de diseño descendente (top-down) o bien el sistema "divide y vencerás".

Partimos del arreglo completo, y buscamos un índice en el interior del intervalo (la mitad, por ejemplo) y el elemento correspondiente a ese índice medio se denominará pivote. Se compara con el valor buscado. Si el resultado de la comparación es verdadero, entonces la búsqueda termina con éxito; de lo contrario, si el valor buscado es menor que el elemento pivote, entonces se reduce el intervalo de búsqueda hacia los valores acotados por el valor mínimo y el valor medio. En el caso contrario, el intervalo se reduce a los valores que se encuentran acotados por el valor medio y el valor máximo del arreglo.

Asumiendo que se tiene un arreglo ordenado: x[1], x[2], …,x[n] y t es el valor a buscar, los pasos a seguir son:

1. Verificar que t > x[1] y t<x[n], de lo contrario t no existe en ese arreglo.

2. Calcular un valor medio entre el mínimo y el máximo, redondeado hacia abajo(k).

3. Si array[k] es igual a t, entonces finaliza la búsqueda. Retorna la posición (k) en el arreglo.

4. Si el valor a buscar está por debajo del valor medio (es menor), es decir, array[k] < t, entonces

haz min = k + 1 y max k - 1. Se descarta la parte superior del vector y se repite el proceso

5. De lo contrario, el valor está por encima del punto medio. Haz max = k – 1, y min = k + 1.

Se descarta la parte inferior del vector y se repite el proceso

Algoritmo busquedaBinaria

inicio

Procedimiento llenar (X,N)

Procedimiento ordenar (X,N)

leer(t)

Min ← 1

Max ← N

Pivot ← entero ((Min + Max) / 2)

mientras (Min =< Max) y (X[Pivot] <> t) hacer

si t < X[Pivot] entonces

Max ← Pivot - 1

si_no

Min ← Pivot + 1

fin_si

Pivot ← entero ((Min + Max) / 2)

fin_mientras

si t = X[Pivot] entonces

escribir('Valor encontrado en ', Pivot)

si_no

escribir('Valor no encontrado')

fin_si

fin

Código C++