Metodo de Busqueda Binaria en Java

El programa tiene un metodo de ordenamiento.


public class BusquedaBinaria { 

public static int busquedaBinaria(int[] Arreglo, int elemento) { 

int i = 0, centro = 0, posicion = 0, inferior = 0, superior = Arreglo.length-1; 

while(inferior <= superior) { 

centro = (superior + inferior) / 2; 

if (Arreglo[centro] == elemento){

 return centro;} else{ if (Arreglo[centro] > elemento){

 superior = centro - 1;}else{ inferior = centro + 1;} 

}

} return -1;

}
public static void main (String[] args) { 

java.util.Scanner Leer = new java.util.Scanner(System.in); 

System.out.print("Tamanio del arreglo:"); 

int tamanioArreglo = Leer.nextInt(); int[] Arreglo = new int[tamanioArreglo]; 

for(int i=0; i<Arreglo.length; i++){ 

System.out.println("Introduce elemento:"); 

Arreglo[i] = Leer.nextInt();

}

int A;

for(int i=0;i<Arreglo.length-1;i++){ 

for(int j=0;j<Arreglo.length-i-1;j++){ 

if(Arreglo[j+1]<Arreglo[j]){ 

A=Arreglo[j+1]; 

Arreglo[j+1]=Arreglo[j]; Arreglo[j]=A; 

} 

} 

} 

System.out.print("Elemento a buscar:" ); 

int elemento = Leer.nextInt(); 

System.out.println("dato"); 

for(int i=0;i<Arreglo.length;i++){ 

System.out.println(Arreglo[i]); 

} 

int posicion = busquedaBinaria(Arreglo, elemento); 

if(posicion == -1)

System.out.println("\nElemento no encontrado"); 

else System.out.println("\nElemento " + elemento + " encontrado en la posicion " + posicion); 

} 

}

Metodo de 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. El vector tiene que estar ordenado.

Ventajas:
La búsqueda binaria es un método eficiente siempre que el vector esté ordenado.
La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista.
Este método funciona a un 100%

Desventajas:
Si los datos del arreglo no están ordenados no hará la búsqueda
Este método Necesita un método de ordenamiento como: Burbuja, Quicksort, shell sort, etc. Para que así funcione bien.

Metodo de busqueda secuencial en Java

public class secuencialdesordenado {
public void buscar()
{
Scanner leer=new Scanner(System.in);
int i=0;
boolean bandera=false;
int x;
int v[]= new int[10];
for(int c=0;c<v.length;c++){
System.out.println("introduce los datos del arreglo");
v[c]=leer.nextInt();
}
System.out.println("introduzca elemento a buscar");
x=leer.nextInt();
do{
if(v[i]==x)
{
bandera=true;
}
else {
bandera=false;
}
i++;
}while(i<v.length && bandera==false);
if(bandera==true){
System.out.println("el elemento esta en la posicion "+ i);
}
else if(bandera==false){
System.out.println("el elemento no esta en la lista");
}
}

Metodo Busqueda 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”.

Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Metodo Shell Sort en Java

public class shell_sort {
public static void shellSort( int b[ ]){
for(int k= b.length/2; k>0; k=k==2?1:(int)( k/2.2)){
for(int i=k;i<b.length; i++ ){
int tmp =b[i];
int j;
for(j=i; j>=k&&tmp<b[j-k]; j-=k){
b[j]=b[j-k]; }
b[j]=tmp;
}
}
}
public static void main(String args[]){
int a[]={321, 6, 1, 234, 213, 4, 5, 123};
System.out.println("Antes del ordenamiento");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
shellSort(a);
System.out.println("\n");
System.out.println("Ordenado por el método Shell");
for (int i=0;i < a.length;i++){
System.out.print(a[i]+" ");
}
}
}

Metodo Shell Sort

El método de Shell es una versión mejorada del método de inserción directa. Recibe ese nombre en honor de su autor, Donald L. Shell, quien lo propuso en 1959. Este método tambien se conoce como inserción con incrementos decrecientes.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño, pero con incrementos decrecientes; así, los elementos quedaran ordenados en el arreglo más rápidamente.

En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño - por ejemplo -, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modifico los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía la clasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de mas de una posición.

El análisis de eficiencia del método de Shell es un problema muy complicado y aun no resuelto. Hasta el momento no se ha podido establecer la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos, es necesario correr el algoritmo para analizar su tiempo de ejecución.

Ventajas:
-No requiere memoria adicional.
-Mejor rendimiento que el método de inserción rápido.
-Fácil implantación.

Desventajas:
-Su funcionamiento puede resultar confuso
-Suele ser un poco lento.
-Realiza numerosas comparaciones e intercambios.

Método QuickSort en Java

public class quicksort {
public static void main(String a[]){
int i;
int array[] = {12,9,4,99,120,1,3,10,13};
System.out.println(" Quick Sort\n");
System.out.println("Valores antes de QuickSort:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
quick_srt(array,0,array.length-1);
System.out.print("\n\n\nValores despues de QuickSort:\n\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
}

public static void quick_srt(int array[],int low, int n){
int lo = low;
int hi = n;
if (lo >= n) {
return;
}
int mid = array[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && array[lo] < mid) {
lo++;
}
while (lo<hi && array[hi] > mid) {
hi--;
}
if (lo < hi) {
int T = array[lo];
array[lo] = array[hi];
array[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quick_srt(array, low, lo);
quick_srt(array, lo == low ? lo+1 : lo, n);
}
}