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

Arrays

Un array en java es un objeto que contiene de cero a más elementos de un mismo tipo, los elementos que contiene son almacenados en el array y se puede acceder a ellos mediante su numeración que comienza con el número 0.

Arrays unidimensionales y bidimensionales

Los arrays representan matrices, en el caso de los de una dimensión a aquellas matrices tipo columna o fila y los bidimensionales a cualquier matriz de "n" filas por "m" columnas.

En el lenguaje Java estas se pueden definir de la siguiente forma:

        
        //Arrays unidimensionales
        int[] vector; // vector[] es un array de valores tipo int
        
        //Arrays bidimensionales
        int[][] matriz; // matriz[][] es un array de valores tipo int[]
         

Como se aprecia, las matrices son arrays de arrays y para declarar cualquier array se debe colocar primero el tipo de dato que almacenarán sea primitivo o tipo objeto, luego dependiendo de la cantidad de dimensiones los corchetes [ ].

Operaciones con arrays

Para crear un array, se debe inicializar el mismo indicando la cantidad de elementos que contendrá o indicando los elementos que va contener de cualquiera de las siguientes maneras

        
        // Sin valores asignados
        byte[] notas = new byte[5]; 
        //Con valores
        String[] cursos = {"Física", "Cálculo", "Filosofía"};
         

Para ir asignando valores dentro del array se puede emplear estructuras repetitivas o manualmente indicando el nombre del array y entre corchetes la posición (conocida como index). Esta posición siempre comienza con cero y su máximo valor es el tamaño del array menos uno.

        
        //Asignación de valores
        notas[0]=20;
        notas[1]=12;
        notas[2]=10;
        notas[3]=15;
        notas[4]=6;
         

Para modificar un valor se realiza el mismo proceso que al asignar valores con el nuevo contenido.

        
        //Modificar un valor
        cursos[1] = "Matemática"; // Cambia 'Cálculo' por 'Matemática'
         

Para poder recorrer un array se pueden emplear estructuras repetitivas "for" con variables de tipo contador o sin estas conocidos en otros lenguajes como "foreach"

        
        //Imprimiendo en consola
        System.out.println("Contenido de notas[]");
        for (int i = 0; i < notas.length; i++) {
            System.out.println(notas[i]);
        }
        
        System.out.println("\nContenido de Cursos[]");
        for (String curso : cursos) {
            System.out.println(curso);
        }
         

Todos los arrays poseen un campo llamado "length" que devuelve el tamaño de este y puede ser empleado para diversas tareas como el límite del contador en una estructura "for", en el segundo caso al recorrer el array se emplea una variable del mismo tipo que el array con un identificador diferente al array, luego dos puntos y el nombre del array, ya no es necesario indicar dentro la posición como sí en el caso del array recorrido mediante una variable de tipo contador.

El programa completo sería:

package test;

public class Arrays {

    public static void main(String[] args) {
        //Creación e inicialización        
        // Sin valores asignados
        byte[] notas = new byte[5]; 
        //Con valores
        String[] cursos = {"Física", "Cálculo", "Filosofía"};
        
        //Asignación de valores
        notas[0]=20;
        notas[1]=12;
        notas[2]=10;
        notas[3]=15;
        notas[4]=6;
        
        //Modificar un valor
        cursos[1] = "Matemática"; // Cambia 'Cálculo' por 'Matemática'
        
        //Imprimiendo en consola
        System.out.println("Contenido de notas[]");
        for (int i = 0; i < notas.length; i++) {
            System.out.println(notas[i]);
        }
        
        System.out.println("\nContenido de cursos[]");
        for (String curso : cursos) {
            System.out.println(curso);
        }
    }
}

Se obtiene un resultado como el siguiente:

Contenido de notas[]
20
12
10
15
6

Contenido de cursos[]
Física
Matemática
Filosofía