Como funcionam busca binária e merge sort para GCSE?

Se você está revisando algoritmos para GCSE Computer Science, quatro nomes aparecem repetidamente: linear search, binary search, bubble sort e merge sort. Bancas examinadoras adoram pedir para você rastrear esses algoritmos manualmente, identificar o tempo de execução ou preencher linhas de pseudocódigo ausentes. Aqui está o que realmente importa para o exame e além.

Linear search: a base

Linear search verifica cada item em uma lista, um de cada vez, até encontrar o alvo ou chegar ao final. Pronto.

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

No pior caso, você verifica cada elemento, então é O(n). No melhor caso, o alvo é o primeiro, então O(1). Examinadores gostam de pedir para você indicar ambos. Linear search funciona em dados não ordenados, que é sua única vantagem real sobre binary search.

Binary search: o que confunde as pessoas

Binary search só funciona em uma lista ordenada. Você compara o alvo ao item do meio. Se o alvo é menor, você descarta a metade superior; se maior, descarta a metade inferior. Repita até encontrá-lo ou ficar sem itens.

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

Isso é O(log n), por isso é dramaticamente mais rápido em conjuntos de dados grandes. Pesquise uma lista ordenada de um milhão de itens e linear search pode precisar de até um milhão de comparações; binary search precisa de cerca de 20. Examinadores frequentemente dão a você uma lista de, digamos, 16 números e pedem para você rastrear quais índices são verificados — pratique isso manualmente com caneta e papel, não apenas na sua cabeça.

Bubble sort: simples mas lento

Bubble sort percorre repetidamente a lista, trocando itens adjacentes se estiverem na ordem errada. Cada passagem completa empurra o maior item não ordenado para sua posição correta no 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])

O pior caso é O(n²) — para cada elemento, você pode escanear quase toda a lista novamente. É raramente usado em software real porque é lento em dados grandes, mas examinadores gostam dele porque rastreá-lo manualmente é viável e ele claramente demonstra a ideia de passagens e trocas repetidas. Saiba como contar o número de comparações e trocas em uma tabela de rastreamento; esse é um item comum no esquema de pontuação.

Merge sort: dividir e conquistar

Merge sort divide a lista pela metade repetidamente até cada sublista ter um item, depois mescla essas sublistas de volta em ordem ordenada.

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)

O passo merge compara os itens frontais de cada metade e escolhe o menor, repetindo até ambas as metades serem usadas. Isso resulta em O(n log n), que vence bubble sort confortavelmente em qualquer coisa exceto listas minúsculas. Questões de GCSE às vezes pedem para você desenhar o diagrama de divisão e mesclagem — uma forma de árvore mostrando a lista dividindo e depois se recombinando. Pratique desenhar isso para uma lista de 8 números para que você seja rápido nele sob condições de exame.

O que examinadores realmente testam

A maioria dos esquemas de pontuação quer que você seja capaz de:

• Rastrear um algoritmo passo a passo e anotar o estado da lista após cada passagem ou comparação.
• Indicar complexidade de tempo em termos de Big O, ou pelo menos descrever em palavras (