Searching: linear and binary · ⁨Busca: linear e binária⁩ — 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).

Português

Encontrando um valor

Uma tarefa comum é pesquisar: se um valor está em um array, e onde?
A resposta usual é o índice onde o encontramos, ou -1 se não estiver lá.
Aprendemos duas formas: busca linear (funciona em qualquer array) e busca binária (precisa de um array ordenado, mas é muito mais 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.

Português

Busca linear

Olhe cada item do índice 0 até o final.
Se o item for igual ao alvo, retorne seu índice imediatamente.
Se o loop terminar sem correspondência, retorne -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.

Português

Quão rápido é a busca linear?

No pior caso (o valor está por último, ou falta), ela verifica todos os itens.
Para uma lista de n itens, são até n verificações. Chamamos isso de tempo linear.
Para arrays pequenos, isso é totalmente aceitável. Para arrays grandes ordenados, podemos fazer melhor.

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.

Português

A busca binária precisa de um array ordenado

Busca binária só funciona quando o array já está ordenado (do menor para o maior).
Ela verifica o item do meio, depois descarta metade do array a cada passo.
Isso é muito mais rápido: um milhão de itens levam cerca de 20 verificações, não um milhão.

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.

Português

A ideia da busca binária

Mantenha dois limites: low (início) e high (fim).
Olhe para o índice do meio mid = (low + high) / 2.
Se a[mid] for igual ao alvo, retorne mid.
Se a[mid] for muito pequeno, o alvo deve estar à direita, então defina low = mid + 1.
Se a[mid] for muito grande, o alvo deve estar à esquerda, então defina high = mid - 1.
Pare quando low ultrapassar high; então o valor não está lá, retorne -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.

Português

Quando um valor falta

Ambas as buscas retornam -1 quando o alvo não está no array.
Para a busca binária, o loop termina quando low > high — os limites cruzaram, então não há mais onde olhar.
Sempre trate o caso de -1 no código que chama uma busca.

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).

Português

Erros comuns

A busca binária precisa de um array ordenado.
Busca linear é O(n); binária é 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.

Português

Agora você tenta

Cada tarefa pré-preenche a estrutura da classe — escreva seu código dentro do main, ou complete o método mostrado.
Pressione Run para compilar e executar, depois Check answer.
Seu código compila e roda no servidor, então até a primeira execução é rápida.

Explore · ⁨Explorar⁩

Linear vs binary search · ⁨Busca linear vs busca binária⁩

Binary search halves the range each step — far fewer checks. · ⁨A busca binária divide o intervalo pela metade a cada passo — muito menos verificações.⁩

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. · ⁨Complete linearSearch(int[] a, int target). Retorne o índice do primeiro item igual a target, ou -1 se não estiver no array. Verifique os itens do índice 0 para cima.⁩

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. · ⁨Clique em Executar para ver a saída aqui.⁩

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. · ⁨Complete binarySearch(int[] a, int target) para um array ordenado. Use limites low/high e verifique o meio a cada passo. Retorne o índice de target, ou -1 se estiver ausente.⁩

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. · ⁨Clique em Executar para ver a saída aqui.⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears. · ⁨Complete countOccurrences(int[] a, int target) que retorna quantas vezes target aparece em a (uma varredura linear). Retorne 0 se nunca aparecer.⁩

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. · ⁨Clique em Executar para ver a saída aqui.⁩

Searching: linear and binary · ⁨Busca: linear e binária⁩

Finding a value

Encontrando um valor

Linear search

Busca linear

How fast is linear search?

Quão rápido é a busca linear?

Binary search needs a sorted array

A busca binária precisa de um array ordenado

The binary search idea

A ideia da busca binária

When a value is missing

Quando um valor falta

Common mistakes

Erros comuns

Now you try

Agora você tenta

Linear vs binary search · ⁨Busca linear vs busca binária⁩

Handout · ⁨Material de apoio⁩

Log in or create account · ⁨Entrar ou criar conta⁩

Your subject · ⁨Sua matéria⁩

All sections · ⁨Todas as seções⁩

Feedback & help · ⁨Feedback & ajuda⁩