Búsqueda y ordenación en Java

Buscar un dato y ordenar una lista son dos de las tareas más repetidas en programación: encontrar un socio por su nombre, ordenar una clasificación por tiempos, mostrar productos del más barato al más caro. Java ya trae métodos que lo hacen, pero en los ciclos de FP se estudian los algoritmos clásicos por dentro, porque enseñan a pensar con arrays y bucles y aparecen en todos los exámenes. En esta lección programarás la búsqueda lineal y binaria, tres métodos de ordenación con su traza, y aprenderás a medir lo rápido que es un algoritmo.

Búsqueda lineal

La búsqueda lineal (o secuencial) es la más sencilla: recorre el array desde el principio y compara cada elemento con el que buscas. Si lo encuentra, devuelve su posición; si llega al final sin encontrarlo, devuelve -1, un valor que no puede ser una posición válida.

public class BusquedaLineal {
    static int busquedaLineal(int[] datos, int buscado) {
        for (int i = 0; i < datos.length; i++) {
            if (datos[i] == buscado) {
                return i;            // encontrado: salimos ya
            }
        }
        return -1;                   // hemos mirado todo y no está
    }

    public static void main(String[] args) {
        int[] dorsales = {27, 4, 91, 15, 63, 8};
        System.out.println(busquedaLineal(dorsales, 63));
        System.out.println(busquedaLineal(dorsales, 50));
    }
}
// 4
// -1

Con textos funciona igual, pero comparando con equals (o equalsIgnoreCase para no distinguir mayúsculas), nunca con ==:

static int buscarSocio(String[] nombres, String buscado) {
    for (int i = 0; i < nombres.length; i++) {
        if (nombres[i].equalsIgnoreCase(buscado)) {
            return i;
        }
    }
    return -1;
}

String[] socios = {"Lucía", "Andrés", "Nerea", "Iker"};
System.out.println(buscarSocio(socios, "nerea")); // 2

Ventaja: funciona con cualquier array, esté ordenado o no. Inconveniente: en el peor caso (el elemento no está o es el último) mira todos los elementos. Con 6 dorsales da igual; con 10 millones de registros, se nota.

Búsqueda binaria

Piensa en cómo buscas una palabra en un diccionario de papel. No empiezas por la primera página: abres por la mitad, miras si la palabra va antes o después, y descartas media mitad de golpe. Eso es la búsqueda binaria, y tiene una condición imprescindible: el array debe estar ordenado.

El algoritmo usa dos índices, inicio y fin, que marcan la zona donde todavía puede estar el dato:

1. Calcula la posición del medio.
2. Si el elemento del medio es el buscado, termina.
3. Si es menor que el buscado, el dato solo puede estar a la derecha: inicio = medio + 1.
4. Si es mayor, solo puede estar a la izquierda: fin = medio - 1.
5. Repite mientras inicio <= fin. Si se cruzan, no está.

static int busquedaBinaria(int[] datos, int buscado) {
    int inicio = 0;
    int fin = datos.length - 1;
    while (inicio <= fin) {
        int medio = (inicio + fin) / 2;
        if (datos[medio] == buscado) {
            return medio;
        } else if (datos[medio] < buscado) {
            inicio = medio + 1;      // descarta la mitad izquierda
        } else {
            fin = medio - 1;         // descarta la mitad derecha
        }
    }
    return -1;
}

int[] precios = {3, 7, 12, 18, 25, 31, 40, 52, 66};
System.out.println(busquedaBinaria(precios, 40)); // 6
System.out.println(busquedaBinaria(precios, 20)); // -1

Traza de la búsqueda binaria

Buscando el 20 en {3, 7, 12, 18, 25, 31, 40, 52, 66}:

Vuelta	inicio	fin	medio	datos[medio]	Decisión
1	0	8	4	25	25 > 20 → fin = 3
2	0	3	1	7	7 < 20 → inicio = 2
3	2	3	2	12	12 < 20 → inicio = 3
4	3	3	3	18	18 < 20 → inicio = 4
—	4	3			inicio > fin: no está, devuelve -1

En cuatro comparaciones ha descartado los nueve elementos. Buscando el 40, solo necesita dos vueltas (medio 4 con valor 25, y medio 6 con valor 40).

Cuánto tarda un algoritmo: la notación O

Para comparar algoritmos no se usan segundos, que dependen del ordenador, sino cuántas operaciones hacen según el número de elementos, n. Esto se expresa con la notación O grande (se lee “o de…”), que indica cómo crece el trabajo cuando crecen los datos:

Notación	Nombre	Qué significa	Ejemplo
O(1)	Constante	Siempre lo mismo, haya los datos que haya	Leer datos[5]
O(log n)	Logarítmica	Cada paso divide el problema a la mitad	Búsqueda binaria
O(n)	Lineal	Mira cada elemento una vez	Búsqueda lineal, sumar un array
O(n²)	Cuadrática	Por cada elemento, recorre todos los demás	Burbuja, selección, inserción

Con números se ve mejor. Operaciones aproximadas en el peor caso:

n	O(log n)	O(n)	O(n²)
10	4	10	100
1.000	10	1.000	1.000.000
1.000.000	20	1.000.000	1.000.000.000.000

Buscar entre un millón de elementos ordenados cuesta unas 20 comparaciones con búsqueda binaria, frente a un millón con la lineal. Y un algoritmo O(n²) que va bien con 1.000 elementos se vuelve inservible con un millón.

Ordenación por burbuja

El método de la burbuja (bubble sort) recorre el array comparando cada elemento con el siguiente. Si están desordenados, los intercambia. Tras la primera pasada, el mayor ha “subido” hasta el final, como una burbuja; tras la segunda, el segundo mayor queda en su sitio, y así sucesivamente.

Para intercambiar dos posiciones hace falta una variable auxiliar, igual que para cambiar el contenido de dos vasos necesitas un tercero:

int aux = a[i];
a[i] = a[i + 1];
a[i + 1] = aux;

El algoritmo completo, con dos mejoras: cada pasada recorre un elemento menos (los últimos ya están colocados) y, si en una pasada no hay ningún intercambio, el array ya está ordenado y se puede parar.

import java.util.Arrays;

public class Burbuja {
    static void burbuja(int[] a) {
        for (int pasada = 0; pasada < a.length - 1; pasada++) {
            boolean huboCambios = false;
            for (int i = 0; i < a.length - 1 - pasada; i++) {
                if (a[i] > a[i + 1]) {
                    int aux = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = aux;
                    huboCambios = true;
                }
            }
            System.out.println("Pasada " + (pasada + 1) + ": " + Arrays.toString(a));
            if (!huboCambios) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        burbuja(new int[] {5, 1, 4, 2, 8});
    }
}
// Pasada 1: [1, 4, 2, 5, 8]
// Pasada 2: [1, 2, 4, 5, 8]
// Pasada 3: [1, 2, 4, 5, 8]

Detalle de la primera pasada sobre [5, 1, 4, 2, 8]:

Compara	¿Intercambia?	Array después
5 y 1	Sí	[1, 5, 4, 2, 8]
5 y 4	Sí	[1, 4, 5, 2, 8]
5 y 2	Sí	[1, 4, 2, 5, 8]
5 y 8	No	[1, 4, 2, 5, 8]

En la tercera pasada no hay cambios, así que el break evita la cuarta. La burbuja es fácil de entender y de recordar, pero es O(n²) y la más lenta de las tres en la práctica.

Ordenación por selección

La selección busca el menor de todo el array y lo pone en la primera posición; luego busca el menor del resto y lo pone en la segunda; y así hasta el final. Hace pocos intercambios (uno por vuelta), pero siempre recorre todo lo que queda.

static void seleccion(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int posMin = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[posMin]) {
                posMin = j;
            }
        }
        int aux = a[i];
        a[i] = a[posMin];
        a[posMin] = aux;
        System.out.println("Paso " + (i + 1) + ": " + Arrays.toString(a));
    }
}

seleccion(new int[] {29, 10, 14, 37, 13});
// Paso 1: [10, 29, 14, 37, 13]
// Paso 2: [10, 13, 14, 37, 29]
// Paso 3: [10, 13, 14, 37, 29]
// Paso 4: [10, 13, 14, 29, 37]

En el paso 1 el menor es el 10 y se cambia por el 29. En el paso 2 el menor del resto es el 13 y se cambia por el 29, que estaba en la posición 1. En el paso 3 el 14 ya está en su sitio y se “intercambia” consigo mismo.

Ordenación por inserción

La inserción es como ordenar las cartas de una mano: coges una carta y la metes en su sitio entre las que ya tienes ordenadas, desplazando a la derecha las que son mayores.

static void insercion(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int actual = a[i];               // la carta que vamos a colocar
        int j = i - 1;
        while (j >= 0 && a[j] > actual) {
            a[j + 1] = a[j];             // desplaza a la derecha
            j--;
        }
        a[j + 1] = actual;               // la deja en su hueco
        System.out.println("Inserto " + actual + ": " + Arrays.toString(a));
    }
}

insercion(new int[] {12, 11, 13, 5, 6});
// Inserto 11: [11, 12, 13, 5, 6]
// Inserto 13: [11, 12, 13, 5, 6]
// Inserto 5: [5, 11, 12, 13, 6]
// Inserto 6: [5, 6, 11, 12, 13]

Fíjate en el paso del 13: como ya es mayor que el 12, el while no se ejecuta ni una vez. Por eso la inserción es muy rápida con arrays casi ordenados: si todo está en su sitio, cada elemento solo se compara una vez y el algoritmo es O(n). Sigue siendo O(n²) en el peor caso (array al revés), pero de los tres métodos clásicos es el que mejor funciona en la práctica.

Comparativa de los tres

Método	Idea	Peor caso	Lo mejor	Lo peor
Burbuja	Intercambiar vecinos desordenados	O(n²)	El más fácil de recordar	El más lento
Selección	Buscar el mínimo y ponerlo delante	O(n²)	Pocos intercambios	Siempre recorre todo
Inserción	Meter cada elemento en su hueco	O(n²)	Muy rápido si está casi ordenado	Muchos desplazamientos si está al revés

Existen algoritmos mucho más rápidos, como quicksort o mergesort, que son O(n log n). Se basan en la recursividad: dividen el array en trozos, los ordenan por separado y los combinan.

Lo que usarás en la vida real: Arrays.sort y binarySearch

En un programa real no escribirás la burbuja: Java ya trae métodos optimizados en la clase Arrays (lo básico lo viste en arrays). Arrays.sort usa internamente algoritmos O(n log n) muy afinados. En una prueba ordenando 100.000 números aleatorios, la burbuja tardó unos 18 segundos y Arrays.sort, unos 40 milisegundos.

int[] tiempos = {58, 42, 71, 39, 66};
Arrays.sort(tiempos);
System.out.println(Arrays.toString(tiempos));       // [39, 42, 58, 66, 71]
System.out.println(Arrays.binarySearch(tiempos, 58)); // 2

Cuando el valor no está, binarySearch no devuelve simplemente -1, sino -(posición donde debería ir) - 1. Así, además de saber que no está, sabes dónde insertarlo para mantener el orden:

int pos = Arrays.binarySearch(tiempos, 50);
System.out.println(pos);                                  // -3
System.out.println("Iría en la posición " + (-pos - 1)); // Iría en la posición 2

Para ordenar de mayor a menor hay que usar un array de objetos (Integer[], no int[]) y pasar un comparador:

Integer[] notas = {6, 9, 4, 7};
Arrays.sort(notas, Collections.reverseOrder());   // import java.util.Collections;
System.out.println(Arrays.toString(notas));       // [9, 7, 6, 4]

Con listas se usan los equivalentes de Collections:

List<String> frutas = new ArrayList<>(List.of("pera", "kiwi", "manzana"));
Collections.sort(frutas);
System.out.println(frutas);                                     // [kiwi, manzana, pera]
System.out.println(Collections.binarySearch(frutas, "manzana")); // 1

Para ordenar objetos propios (alumnos por nota, productos por precio) necesitas decirle a Java cómo compararlos, con Comparable o Comparator: lo tienes en Comparable y Comparator.

¿Qué uso en cada caso?

Situación	Qué usar
Buscar una vez en datos sin ordenar	Búsqueda lineal
Buscar muchas veces en los mismos datos	Ordenar una vez y usar búsqueda binaria
Ordenar en un programa real	Arrays.sort o Collections.sort / lista.sort(...)
Comprobar si algo existe muy a menudo	Un HashSet o un HashMap (mapas y conjuntos)
Examen o ejercicio de clase	Burbuja, selección o inserción escritos a mano

Ordenar cuesta más que una búsqueda lineal, así que no ordenes para buscar una sola vez: compensa cuando vas a buscar muchas veces sobre los mismos datos.

Errores frecuentes

• Usar búsqueda binaria en un array desordenado. No da error: devuelve un resultado sin sentido. Ordena antes.
• Escribir while (inicio < fin) en la búsqueda binaria. Falla cuando el elemento está justo donde inicio y fin coinciden; la condición es <=.
• Olvidar + 1 y - 1 al mover los índices. Con inicio = medio el bucle puede quedarse atascado para siempre.
• Intercambiar sin variable auxiliar. a[i] = a[j]; a[j] = a[i]; deja los dos con el mismo valor.
• Salirse del array en la burbuja. El bucle interno compara a[i] con a[i + 1], así que debe llegar hasta length - 1, no hasta length.
• Comparar textos con == en la búsqueda. Usa equals.
• Creer que binarySearch devuelve siempre -1 si no encuentra el valor: devuelve un número negativo que indica dónde iría.

Resumen

Concepto	Clave
Búsqueda lineal	Mira uno a uno; vale para cualquier array; O(n)
Búsqueda binaria	Divide a la mitad cada vez; solo con datos ordenados; O(log n)
Burbuja	Intercambia vecinos; el mayor sube al final en cada pasada; O(n²)
Selección	Coloca el mínimo del resto en cada posición; O(n²)
Inserción	Mete cada elemento en su hueco; rápida si está casi ordenado
Notación O	Cómo crece el trabajo al crecer los datos
Arrays.sort	Ordena un array en el sitio, O(n log n)
Arrays.binarySearch	Posición del valor, o -(hueco) - 1 si no está
Collections.sort / binarySearch	Lo mismo para listas

Con los arrays dominados, es hora de crear tus propios tipos de datos: empieza con clases y objetos.

static int busquedaBinaria(int[] datos, int buscado) {
    int inicio = 0, fin = datos.length - 1;
    while (inicio <= fin) {
        int medio = (inicio + fin) / 2;
        if (datos[medio] == buscado) return medio;
        else if (datos[medio] < buscado) inicio = medio + 1;
        else fin = medio - 1;
    }
    return -1;
}

int[] tiempos = {39, 42, 58, 66, 71};
System.out.println(Arrays.binarySearch(tiempos, 60));

int[] a = {3, 9};
a[0] = a[1];
a[1] = a[0];
System.out.println(Arrays.toString(a));