INTEGRANTES DEL EQUIPO:
Italia Arango Roque
Berenice Sánchez García
Cristian Mayoral Cruz
Oscar Raúl Santiago Ortiz
Maximiliano Sánchez Hernández

Método de Búsqueda Secuencial
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave. Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista.
image5_1.gif (4381 bytes)
image5_1.gif (4381 bytes)

La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones. Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.

Mejoras en la eficiencia de la búsqueda secuencial
1)Muestreo de acceso
Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas. 2)Movimiento hacia el frente
Este esquema consiste en que la lista de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el.
3)Transposición
Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre mas accesos tenga el registro, mas rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere mas tiempo de actividad para reorganizar al conjunto de registros . Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.
4)Ordenamiento

Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

EJEMPLO DE BÚSQUEDA SECUENCIAL
El siguiente programa cumple con los siguientes requerimientos:
  • Crea un menú de opciones (INSERTAR, CONSULTAR, ELIMINAR Y FINALIZAR).
  • INSERTAR: almacena el nombre de personas en vectores estáticos tipo String de tamaño 50.
  • CONSULTAR: Utilizando el algoritmo de búsqueda secuencial pide el nombre y si lo encuentra imprime un mensaje de encontrado, en caso contrario un mensaje de no localizado.
  • ELIMINAR: Utilizando el algoritmo de búsqueda secuencial pide el nombre y si lo encuentra imprime un mensaje de encontrado y elimina el nombre ajustando el vector para no dejar espacios en blanco, en caso contrario un mensaje de no localizado.
  • FINALIZAR: Imprime los nombres almacenado y sale del programa.


import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BusquedaSecuencial {

static BufferedReader br = null;static String N= "";static int n=0;static String[] Nombre = new String[50];static String[] APaterno = new String[50];static String[] AMaterno = new String[50];

public static void main (String args[]){br = new BufferedReader(new InputStreamReader(System.in));

do{menu();}while(Integer.parseInt(N)!=4);}

public static void menu(){do{System.out.println("Selecciona una de las opciones del menú: \n "+ "1- INSERTAR \n "+ "2- CONSULTAR "+ "\n 3- ELIMINAR \n "+ "4- FINALIZAR");try{N = br.readLine();}catch(Exception e){e.printStackTrace();}}while(!esEntero(N) || conversor(N)<=0 || conversor(N)>=5 );

switch(Integer.parseInt(N)){case 1:insertar();break;case 2:consultar();break;case 3:eliminar();break;case 4:imprimir();break;}}

public static void consultar(){if(n>0){String nombre="";int eureka=0;

try{System.out.println("Ingresa el Nombre : ");nombre = br.readLine();}catch(Exception e){e.printStackTrace();}

for(int i=0; i<n; i++){if(Nombre[i].equals(nombre)){eureka=1;}}if(eureka==1){System.out.println("Nombre encontrado!!!!!. ");}else{System.out.println("Nombre NO localizado!!!!!. ");}}else{System.out.println("No hay elementos en la lista. ");}

}

public static boolean esEntero(String cad) {for(int i = 0; i<cad.length(); i++)if( !Character.isDigit(cad.charAt(i)) )return false;

return true;}

public static int conversor(String x){int valor=0;

try{valor= Integer.parseInt(x);}catch(NumberFormatException e){System.out.println("Valor invalido");}

return valor;}

public static void insertar(){

if(n<50){System.out.println("Leyendo datos de la persona: " + (n+1));

try{System.out.println("Ingresa el Apellido Paterno: ");APaterno[n] = br.readLine();}catch(Exception e){e.printStackTrace();}

try{System.out.println("Ingresa el Apellido Materno: ");AMaterno[n] = br.readLine();}catch(Exception e){e.printStackTrace();}

try{System.out.println("Ingresa el nombre: ");Nombre[n] = br.readLine();}catch(Exception e){e.printStackTrace();}

n++;}else{System.out.println("El vector esta lleno, elimina personas para poder insertar");}

}

public static void eliminar(){String nombre="";int encontrados=0;

if(n>0){

try{System.out.println("Ingresa el Nombre : ");nombre = br.readLine();}catch(Exception e){e.printStackTrace();}

for(int i=0; i<n; i++){if(Nombre[i].equals(nombre)){encontrados++;for(int j=i; j<n; j++){Nombre[j]=Nombre[j+1];APaterno[j]=APaterno[j+1];AMaterno[j]=AMaterno[j+1];}i--;n--;}}if(encontrados>0){System.out.println("Nombre encontrado, procediendo a eliminar!!!!!. ");}else{System.out.println("Nombre NO localizado!!!!!. ");}}else{System.out.println("No hay elementos a eliminar.");}

}

public static void imprimir(){if(n>0){System.out.println("Apellido paterno Apellido Materno Nombre");for(int i=0; i<n; i++){System.out.print(i+1 + ".- " + APaterno[i] + "\t");System.out.print(AMaterno [i] + "\t");System.out.print(Nombre [i] + ".");System.out.println();}}}

}