La operación de buscar un dato dentro de un conjunto dado es una de las operaciones más frecuentes dentro del proceso de datos.
Clasificaremos los algoritmos de búsqueda en función de si e conjunto de datos sobre lo que se extiende la búsqueda está ordenado o no.(Isabel Gallego Férnandez y Manuel Medina Llinás)
Búsqueda Secuencial
El método de búsqueda secuencial es el mas sencillo y se debe utilizar si el conjunto de datos sobre el que se extiende la búsqueda no está ordenado siguiendo criterio alguno. Como su nombre indica, consiste en recorrer el conjunto de datos uno a uno y comparar cada rato con el valor buscado hasta encontrarlo, si es que existe, o hasta el último dato sin éxito en la búsqueda, en el caso que no exista.(Isabel Gallego Férnandez y Manuel Medina Llinás)
Búsqueda Binaria
En el caso de buscar sobre un conjunto ordenado, es posible optimizar el criterio de búsquedas gracias a esa ordenación. Estos métodos de búsqueda son muy eficientes, sobre todo para grandes cantidades de datos ; es por esta razón que se suelen utilizar incluso sobre conjuntos de datos no ordenados, sometiéndolos a un proceso de ordenación previo a la búsqueda propiamente dicha. Uno de estos métodos, el mas popular y sencillo de diseñar, es el método de búsqueda binaria o dicotómica, que estudiaremos en este apartado.
La búsqueda binaria se basa en aprovechar el hecho de que se trata de datos ordenados para extender la búsqueda únicamente a aquella porción de los datos donde, si el dato existe es seguro que se encuentra.(Isabel Gallego Férnandez y Manuel Medina Llinás)
CLASE BUSQUEDAS
package practica2;
public class busqueda {
int max = 100;
int vector[];
int indice = 0;
public void llenarVector(int tamanio) {
indice=0;
vector= new int[max];
while (this.indice < tamanio) {
vector[this.indice++] = (int) (Math.random() * 20);
}
}
public void Mostrar() {
for (int i = 0; i < this.getIndice(); i++) {
System.out.println("Vector [" + i + "] = " + vector[i]);
}
}
public void busquedaSecuencial(int numero) {
int band = 0;
for (int i = 0; i < this.getIndice(); i++) {
if (numero == vector[i]) {
System.out.println("el numero esta en la posicion [" + i + "]");
band++;
}
}
if (band == 0) {
System.out.println("no existe el numero dentro del vector ");
}
System.out.println("band " + band);
}
public int busquedaBinaria(int numero) {
int inicio = 0;
int fin = this.getIndice() - 1;
int posicion;
while (inicio <= fin) {
posicion = (inicio + fin) / 2;
if (vector[posicion] == numero) {
return posicion;
} else if (vector[posicion] < numero) {
inicio = posicion + 1;
} else {
fin = posicion - 1;
}
}
return -1;
}
public int getIndice() {
return indice;
}
public int[] getVector() {
return vector;
}
public void Intercambiar(int vector[], int i, int j) {
int aux;
aux = vector[j];
vector[j] = vector[i];
vector[i] = aux;
}
public void ordenamientoSeleccion() {
int i, j, posicion, menor;
for (i = 0; i < this.getIndice(); i++) {
menor = vector[i];
posicion = i;
for (j = i + 1; j < this.getIndice(); j++) {
if (vector[j] < menor) {
menor = vector[j];
posicion = j;
}
}
if (posicion != i) {
Intercambiar(vector, i, posicion);
}
}
}
}
CLASE MAIN
package practica2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
busqueda bus = new busqueda();
System.out.println("Ingrese el tamanio del vector : ");
bus.llenarVector(Integer.parseInt(br.readLine()));
bus.Mostrar();
bus.ordenamientoSeleccion();
System.out.println("");
bus.Mostrar();
System.out.println("Ingrese el numero a buscar : ");
String numeroo = br.readLine();
int numero = Integer.parseInt(numeroo);
System.out.println("-----busqueda de secuencial-----");
bus.busquedaSecuencial(numero);
System.out.println("-----busqueda binaria-----");
int busquedaBinaria = bus.busquedaBinaria(numero);
if (busquedaBinaria != -1) {
System.out.println(" existe en la posicion : " + busquedaBinaria);
} else {
System.out.println("no se encuentra");
}
}
}
