¿Cómo funcionan la búsqueda binaria y el ordenamiento por mezcla para GCSE?

Si estás repasando algoritmos para GCSE Computer Science, cuatro nombres aparecen una y otra vez: linear search, binary search, bubble sort y merge sort. A los examinadores les encanta pedirte que traces estos a mano, identifiques el tiempo de ejecución o completes líneas faltantes de pseudocódigo. Aquí está lo que realmente importa para el examen y más allá.

Linear search: la línea base

Linear search revisa cada elemento en una lista, uno a la vez, hasta encontrar el objetivo o llegar al final. Eso es todo.

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

En el peor caso, revisas cada elemento, así que es O(n). En el mejor caso, el objetivo está primero, así que es O(1). A los examinadores les gusta pedirte que indiques ambos. Linear search funciona con datos sin ordenar, que es su única ventaja real sobre binary search.

Binary search: la que confunde a la gente

Binary search solo funciona en una lista ordenada. Comparas el objetivo con el elemento del medio. Si el objetivo es más pequeño, descartas la mitad superior; si es más grande, descartas la mitad inferior. Repite hasta encontrarlo o quedarte sin elementos.

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

Esto es O(log n), por lo que es dramáticamente más rápido en conjuntos de datos grandes. Busca en una lista ordenada de un millón de elementos y linear search podría necesitar hasta un millón de comparaciones; binary search necesita unos 20. Los examinadores comúnmente te dan una lista de, digamos, 16 números y te piden que traces qué índices se revisan — practica esto a mano con lápiz y papel, no solo en tu cabeza.

Bubble sort: simple pero lento

Bubble sort recorre la lista repetidamente, intercambiando elementos adyacentes si están en el orden incorrecto. Cada paso completo coloca el elemento más grande sin ordenar en su posición correcta al final.

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

El peor caso es O(n²) — para cada elemento, podrías escanear casi toda la lista de nuevo. Se usa raramente en software real porque es lento con datos grandes, pero a los examinadores les gusta porque tracerlo a mano es manejable y muestra claramente la idea de pasos repetidos e intercambios. Sabe cómo contar el número de comparaciones e intercambios en una tabla de traza; ese es un elemento común de la rúbrica de calificación.

Merge sort: divide y conquista

Merge sort divide la lista por la mitad repetidamente hasta que cada sublista tiene un elemento, luego fusiona esas sublistas de nuevo en orden.

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

El paso merge compara los primeros elementos de cada mitad y elige el más pequeño, repitiendo hasta que ambas mitades se usen. Esto da O(n log n), que supera a bubble sort cómodamente en cualquier cosa excepto listas muy pequeñas. Las preguntas de GCSE a veces te piden que dibujes el diagrama de división y fusión — una forma de árbol mostrando la lista dividiéndose hacia abajo y luego recombinándose. Practica dibujar esto para una lista de 8 números para que sea rápido bajo condiciones de examen.

Qué los examinadores realmente evalúan

La mayoría de las rúbricas de calificación quieren que seas capaz de:

• Trazar un algoritmo paso a paso y escribir el estado de la lista después de cada paso o comparación.
• Indicar complejidad de tiempo en términos Big O, o al menos describirlo en palabras (