Algoritmos de búsqueda en Java.

En lo concerniente al manejo de datos, es de suma importancia conocer los métodos que se suelen usar para localizar elementos en una estructura de datos. Para facilitar las cosas en este post se usarán vectores que contienen números.

Búsqueda secuencial o lineal (Linear Search)

Es posiblemente el más sencillo, de orden de complejidad lineal. Consiste en desplazarse uno a uno por cada elemento del vector mientras se compara con el que estamos buscando. El proceso bien puede finalizar cuando se encuentra o cuando termina de recorrer el vector.

Cabe aclarar que en Java los índices en los vectores comienza en cero, de manera que en el ejemplo, el índice 1 alberga un int de valor 2.

Lo que imprime el algoritmo es:

6
-1

 /*Busca un elemento ingresado recorriendo
 *linealmente el vector donde se buscará este primero.
 */

public class LinearSearch {

 // Retorna el índice donde se halla el elemento que se buscó, o -1 si este no está.
    public int find(int[] vector,int value){
     for(int i=0; i < vector.length;i++){
      if(value==vector[i])
       return i;
     }

 return -1;
    }

    public static void main(String[] args){

     LinearSearch ls = new LinearSearch();
  int []vector = { 1, 2, 3, 4 , 5,6 ,7, 8, 9, 10};
  int elemento1 = 7;
  int elemento2 = 12;

  System.out.println(ls.find(vector,elemento1));
  System.out.println(ls.find(vector,elemento2));


    }


}

Búsqueda binaria o dicotómica (Binary Search)

Más eficiente que el de búsqueda lineal, este algoritmo  tiene orden de complejidad logarítmica, O(log n) aunque tiene un precio a pagar por esta ventaja, y es que para que sea útil este mecanismo, el vector a tratar debe estar organizado. Entonces de lo anterior se deduce que es ideal a usar en situaciones donde el vector posee muchos elementos.

Asumiremos que contamos con un vector organizado ascendentemente ya sea que se haya aplicado otro algoritmo para esto.

Explicación del algoritmo: El número que buscamos -target- se compara con el 'midPoint', usualmente éste se toma como el centro del intervalo acotado por 'bottom' y 'top'.
Si el target es menor que midPoint, en el próximo ciclo, la búsqueda se efectuará en la primera mitad del vector. En cambio si target es mayor que midPoint, en el siguiente ciclo no se tendrá en cuenta la primera mitad. Así transcurren los ciclos, partiendo el intervalo de búsqueda.
Si se tuviese un vector ordenado descendentemente sólo se necesita reemplazar los dos primeros condicionales por <  y > respectivamente.

El algoritmo imprime:
0
-1

public class BinarySearch {



 public int find(int[] vectorOrganizado , int target)  {

  int top = vectorOrganizado.length - 1 ;
  int bottom = 0;
  int midPoint;

  while(bottom<=top){
   //se toma la parte entera, es decir, de 2.5 se toma el 2.
   midPoint = (bottom + top)/2;
   if(target > vectorOrganizado[midPoint])
    bottom = midPoint + 1 ;
   else if (target < vectorOrganizado[midPoint])
    top = midPoint - 1;
   else
    return midPoint;

  }
  return -1;
 }

 public static void main(String []args){
  BinarySearch bs = new BinarySearch();
  int [] vect = {1,2,3,4,5,6,7,8,9,10};
  int value1 = 1 ;
  int value2 = 22;
  System.out.println(bs.find(vect,value1));
  System.out.println(bs.find(vect,value2));

 }

}