Searching: linear and binary · ⁨Búsqueda: lineal y binaria⁩ — Java for AP CS A

English

Finding a value

A common job is to search: is a value in an array, and where?
The usual answer is the index where we found it, or -1 if it is not there.
We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

Español

Encontrar un valor

Un trabajo común es buscar: ¿hay un valor en un array y, ¿dónde está?
La respuesta habitual es el índice donde se encontró, o -1 si no está.
Aprendemos dos formas: búsqueda lineal (funciona con cualquier array) y búsqueda binaria (necesita un array ordenado, pero es mucho más rápida).

English

Linear search

Look at each item from index 0 to the end.
If the item equals the target, return its index right away.
If the loop finishes with no match, return -1.

Español

Búsqueda lineal

Revisa cada elemento desde el índice 0 hacia el final.
Si el elemento es igual al objetivo, devuelve su índice de inmediato.
Si el bucle termina sin encontrar coincidencia, devuelve -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {4, 8, 15, 16, 23};
        int target = 15;
        int found = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                found = i;
                break;       // stop early, we have it
            }
        }
        System.out.println(found);   // 2
    }
}

English

How fast is linear search?

In the worst case (the value is last, or missing) it checks every item.
For a list of n items that is up to n checks. We call this linear time.
For small arrays this is totally fine. For huge sorted arrays we can do better.

Español

¿Qué tan rápido es la búsqueda lineal?

En el peor caso (el valor está al final o no existe) revisa todos los elementos.
Para una lista de n elementos, puede requerir hasta n comprobaciones. A esto lo llamamos tiempo lineal.
Para arrays pequeños esto es totalmente aceptable. Para arrays grandes y ordenados podemos hacer mejor.

English

Binary search needs a sorted array

Binary search only works when the array is already sorted (small to large).
It checks the middle item, then throws away half the array each step.
That is much faster: a million items take about 20 checks, not a million.

Español

La búsqueda binaria necesita un array ordenado

La búsqueda binaria solo funciona cuando el array ya está ordenado (de menor a mayor).
Revisa el elemento del medio, luego descarta la mitad del array en cada paso.
Eso es mucho más rápido: un millón de elementos toma alrededor de 20 comprobaciones, no un millón.

English

The binary search idea

Keep two bounds: low (start) and high (end).
Look at the middle index mid = (low + high) / 2.
If a[mid] equals the target, return mid.
If a[mid] is too small, the target must be on the right, so set low = mid + 1.
If a[mid] is too big, the target must be on the left, so set high = mid - 1.
Stop when low passes high; then the value is not there, return -1.

Español

La idea de la búsqueda binaria

Mantén dos límites: low (inicio) y high (final).
Mira el índice del medio mid = (low + high) / 2.
Si a[mid] es igual al objetivo, devuelve mid.
Si a[mid] es demasiado pequeño, el objetivo debe estar a la derecha, así que ajusta low = mid + 1.
Si a[mid] es demasiado grande, el objetivo debe estar a la izquierda, así que ajusta high = mid - 1.
Detente cuando low supere a high; entonces el valor no está, devuelve -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38};   // sorted!
        int target = 16;

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;     // go right
            } else {
                high = mid - 1;    // go left
            }
        }
        System.out.println(found);   // 4
    }
}

English

When a value is missing

Both searches return -1 when the target is not in the array.
For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
Always handle the -1 case in code that calls a search.

Español

Cuando falta un valor

Ambas búsquedas devuelven -1 cuando el objetivo no está en el array.
En la búsqueda binaria, el bucle termina cuando low > high — los límites se han cruzado, por lo que no queda nada más donde buscar.
Siempre maneja el caso de -1 en el código que llame a una búsqueda.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12};   // sorted
        int target = 7;            // not in the array

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(found);   // -1
    }
}

English

Common mistakes

Binary search needs a sorted array.
Linear search is O(n); binary is O(log n).

Español

Errores comunes

La búsqueda binaria necesita un array ordenado.
La búsqueda lineal es O(n); la binaria es O(log n).

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Español

Ahora tú intentas

Cada tarea prellena la plantilla de clase — escribe tu código dentro de main, o completa el método mostrado.
Presiona Run para compilar y ejecutar, luego Check answer.
Tu código se compila y ejecuta en el servidor, así que incluso la primera ejecución es rápida.

Explore · ⁨Explorar⁩

Linear vs binary search · ⁨Búsqueda lineal vs. búsqueda binaria⁩

Binary search halves the range each step — far fewer checks. · ⁨La búsqueda binaria reduce a la mitad el rango en cada paso — mucho menos comprobaciones.⁩

Complete linearSearch(int[] a, int target). Return the index of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward. · ⁨Completa linearSearch(int[] a, int target). Devuelve el índice del primer elemento igual a target, o -1 si no está en el array. Revisa los elementos desde el índice 0 hacia arriba.⁩

public class SearchUtil {
    // Return the index of target, or -1 if not found.
    public static int linearSearch(int[] a, int target) {
        return -1;   // change this
    }
}

Click Run to see the output here. · ⁨Haz clic en Ejecutar para ver la salida aquí.⁩

Complete binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing. · ⁨Completa binarySearch(int[] a, int target) para un array ordenado. Usa los límites low/high y revisa el medio en cada paso. Devuelve el índice de target, o -1 si no se encuentra.⁩

public class SearchUtil {
    // Binary search on a sorted array. Return index or -1.
    public static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        // your loop here
        return -1;
    }
}

Click Run to see the output here. · ⁨Haz clic en Ejecutar para ver la salida aquí.⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears. · ⁨Completa countOccurrences(int[] a, int target) que devuelva cuántas veces aparece target en a (una exploración lineal). Devuelve 0 si nunca aparece.⁩

public class SearchUtil {
    // Count how many times target appears in a.
    public static int countOccurrences(int[] a, int target) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Haz clic en Ejecutar para ver la salida aquí.⁩

Searching: linear and binary · ⁨Búsqueda: lineal y binaria⁩

Finding a value

Encontrar un valor

Linear search

Búsqueda lineal

How fast is linear search?

¿Qué tan rápido es la búsqueda lineal?

Binary search needs a sorted array

La búsqueda binaria necesita un array ordenado

The binary search idea

La idea de la búsqueda binaria

When a value is missing

Cuando falta un valor

Common mistakes

Errores comunes

Now you try

Ahora tú intentas

Linear vs binary search · ⁨Búsqueda lineal vs. búsqueda binaria⁩

Handout · ⁨Material⁩

Log in or create account · ⁨Iniciar sesión o crear cuenta⁩

Your subject · ⁨Tu asignatura⁩

All sections · ⁨Todas las secciones⁩

Feedback & help · ⁨Comentarios y ayuda⁩