Búsqueda en vector

PROGRAMACIÓN ORIENTADA A OBJETOS 1

VectoresBúsqueda

Ing. Magda Paola Fernández Echeverri

Tabla de contenido

Búsqueda Lineal

Búsqueda Binaria

Búsqueda Lineal

La búsqueda lineal en un arreglo, consiste en la implementación de un proceso iterativo que recorre todo el arreglo .

Se debe contar con un índice que inicia en 0 e incrementa en cada iteración. Y con la condición que permita comparar la variable que contiene el valor a buscar contra el contenido del arreglo.

Ejemplo

Variable

15

Dato_buscar

• Guardemos dentro del vector: multiplos de 5 posiciones , los múltiplos de 5.

Vector unidimensional multiplos

5 10 15 20 25

0 1 2 3 4Índice

Valores

• La variable Dato_buscar contendrá el valor a buscar dentro del arreglo multiplos.

• Si el valor a buscar es igual al valor del arreglo en índice actual. Debe retornar el valor del índice. En nuestro ejemplo el valor que retorna es 2

Vector unidimensional multiplos

5 10 15 20 25

0 1 2 3 4Índice

15Variable

Dato_buscar

• Se debe compara la variable Dato_buscar con cada uno de los valores que se encuentran en el arreglo multiplos.

Vector unidimensional multiplos

5 10 15 20 25

0 1 2 3 4Índice

8Variable

Dato_buscar

• Si al compara todo el arreglo en ningún caso encuentra el valor, retorna el valor -1.

como vemos el valor a buscar es 8 y no se encuentra en el arreglo multiplos.

Veamos el ejemplo en JAVA• Se crea la clase arreglo_multiplos como se ve en la imagen:

• Al correr el programa se vería por consola:

• Ahora se crea el método buscar en la clase arreglos_multiplos

• Como el método buscar se creo fuera del método main, se debe instanciar la clase arreglo_multiplos dentro de main, para llamar el metodo buscar.

arreglo_multiplos todo= new arreglo_multiplos();int indice= todo.buscar(multiplos, 15);

System.out.println("El indice del valor 15 es: " + indice);

Se llama el metodo buscar y se envían los valores del arreglo y el valor a buscar que en esta caso es 15.

• Al correr el programa saldría por consola:

• Si en lugar de buscar 15 lo cambiamos por 30, un valor que no se encuentra en el vector:

• Al correr el programa saldría por consola:

• Retornaría el valor de -1

Búsqueda BinariaEs la implementación de un proceso recursivo que recibe el arreglo y el valor que se desea buscar . Esta búsqueda debe realizarse con valores ordenados. Se inicia consultando el valor ubicado en la mitad del arreglo.

Si el valor a buscar es igual se retorna al índice.Si el valor es menor, se hace el llamado recursivo realizando la búsqueda con los valores desde la posición inicial, hasta la

posición anterior a la mitad.Pero si no hay elementos entre estas posiciones , retorna -1.

Si el valor a buscar es mayor, se hace el llamado recursivo realizando la búsqueda con los valores desde la posición

siguiente a la mitad hasta la última posición; pero si no hay elementos entre estas posiciones retorna -1.

Ejemplo

Vector unidimensional

multiplos

0 1 2 3 4 5 6 7 8 9

Posición Inicial

30 35 40 45 505 10 15 20 25

Int multiplos[ ] = new int [10];

• Guardemos dentro del vector: multiplos de 10 posiciones , los múltiplos del 5.

Índice

Posición Final

posFin= multiplos.length -1posIni= 0

Posición centro

poscen= (posIni+posFin) / 2

• Si el valor a buscar es igual que el valor que se encuentra en la mitad, retorna indice.

30 35 40 45 505 10 15 20 25

multiplos

15Variable

Dato_buscar

0 1 2 3 4 5 6 7 8 9

Posición centro

if (Dato_buscar == multiplos[poscen ]){ return poscen;}

poscen= (posIni+posFin) / 2

• Si el valor a buscar no es igual al valor del arreglo en la posición centro, se pregunta si es menor que la posición centro y si no es menor o igual a posición inicial de esta forma buscar solo en esta parte del vector

30 35 40 45 505 10 15 20 25

0 1 2 3 4 5 6 7 8 9

‘

posIni= 0 poscen= (posIni+posFin) / 2posFin= multiplos.length -1

• De lo contrario si no es menor que posición centro buscara después de la mitad, entre centro + 1 y posición final

30 35 40 45 505 10 15 20 25

0 1 2 3 4 5 6 7 8 9‘

posIni= 0 poscen= (posIni+posFin) / 2 posFin= multiplos.length -1

Veamos el ejemplo en JAVA

• Al correr el programa saldría por consola cuando el numero a buscar es 15:

BibliografíaFLOREZ FERNANDEZ, H. (2012). “Arreglos, Matrices y Colecciones” en Flórez Fernández, H. Programación Orientada a Objetos usando JAVA. Ecoe Ediciones. España. P. 75 - 78