Métodos de búsqueda

Búsqueda secuencial o lineal

Consiste en recorrer una estructura de datos comparando cada elemento con el valor buscado, si el elemento buscado se encuentra al inicio, el tiempo de búsqueda será muy corto, pero será cada vez más largo mientras el elemento se encuentre más cerca del final o no se encuentre.

Algoritmo de implementación

package busqueda;

public class Busca {

    public static Integer Secuencial(Integer[] data, int valor) {
        Integer pos = null;
        for (int i = 0; i < data.length; i++) {
            if (valor == data[i]) {
                pos = i;
                break;
            }
        }
        return pos;
    }
}

Aplicando el algoritmo a un Array

package test;

import busqueda.Busca;

public class TestBusqueda {

    public static void main(String[] args) {
        Integer[] datos = {2, 255, 10, 0, 11, 1172, 1};
        System.out.println("Array: " + Arrays.toString(datos));
        
        //Búsqueda de la posición de forma secuencial		
        Integer index = Busca.Secuencial(datos, 11); // Busca 11
        System.out.println("Buscando 11 ...");
        //Mostrar resultado
        if (index != null) {
            System.out.println("Elemento encontrado en la posición " + index);
        } else {
            System.out.println("Elemento no encontrado");
        }
		
        index = Busca.Secuencial(datos, 12); // Busca 12
        System.out.println("Buscando 12 ...");
        //Mostrar resultado
        if (index != null) {
            System.out.println("Elemento encontrado en la posición " + index);
        } else {
            System.out.println("Elemento no encontrado");
        }
    }
}

El resultado sería el siguiente:

Array: [2, 255, 10, 0, 11, 1172, 1]

Buscando 11 ...
Elemento encontrado en la posición 4

Buscando 12 ...
Elemento no encontrado

Búsqueda binaria

Consiste en recorrer una estructura de datos dividiéndola constantemente en dos partes hasta encontrar la coincidencia de búsqueda. Este método requiere que la estructura de datos este previamente ordenada de forma ascendente o descedente.

Algoritmo de implementación

package busqueda;

public class Busca {

    public static Integer Binario(Integer[] data, Integer valor) {
        int li = 0;
        int ls = data.length;
        while (li <= ls) {
            int lm = (ls - li) / 2 + li;
            if (data[lm] < valor) {
                li = lm + 1;
            } else if (data[lm] > valor) {
                ls = lm - 1;
            } else {
                return lm;
            }
        }
        return null;
    }
}

Aplicando el algoritmo a un Array

package test;

import busqueda.Busca;
import java.util.Arrays;

public class TestBusqueda {

    public static void main(String[] args) {
        Integer[] datos = {2, 255, 10, 0, 11, 1172, 1};
        System.out.println("Array: " + Arrays.toString(datos));
        
        //Búsqueda de la posición por búsqueda binaria
        Arrays.sort(datos); // Ordenamiento de datos
        System.out.println("Array ordenado: " + Arrays.toString(datos));
        
        Integer index = Busca.Binario(datos, 172); 
        System.out.println("Buscando 172 ..."); 
        //Mostrar resultado
        if (index != null) {
            System.out.println("Elemento encontrado en la posición " + index);
        } else {
            System.out.println("Elemento no encontrado");
        }
        
        index = Busca.Binario(datos, 255);
        System.out.println("Buscando 255 ...");
        //Mostrar resultado
        if (index != null) {
            System.out.println("Elemento encontrado en la posición " + index);
        } else {
            System.out.println("Elemento no encontrado");
        }
    }
}

El resultado sería el siguiente:

Array: [2, 255, 10, 0, 11, 1172, 1]
Array ordenado: [0, 1, 2, 10, 11, 255, 1172]

Buscando 172 ...
Elemento no encontrado

Buscando 255 ...
Elemento encontrado en la posición 5