Busca: linear e binária
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
-1se 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).
Busca linear
- Olhe cada item do índice
0até 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
}
}
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
nitens, são aténverificações. Chamamos isso de tempo linear. - Para arrays pequenos, isso é totalmente aceitável. Para arrays grandes ordenados, podemos fazer melhor.
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.
A ideia da busca binária
- Mantenha dois limites:
low(início) ehigh(fim). - Olhe para o índice do meio
mid = (low + high) / 2. - Se
a[mid]for igual ao alvo, retornemid. - Se
a[mid]for muito pequeno, o alvo deve estar à direita, então definalow = mid + 1. - Se
a[mid]for muito grande, o alvo deve estar à esquerda, então definahigh = mid - 1. - Pare quando
lowultrapassarhigh; 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
}
}
Quando um valor falta
- Ambas as buscas retornam
-1quando 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
-1no 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
}
}
Erros comuns
- A busca binária precisa de um array ordenado.
- Busca linear é O(n); binária é O(log n).
Agora você tenta
- Cada tarefa pré-preenche a estrutura da classe — escreva seu código dentro do main, ou complete o método mostrado.
- Use Check answer para compilar seu código com os testes fornecidos e visualizar os resultados. Mantenha as interfaces da classe e do método mostradas no modelo.
- Seu código compila e roda no servidor, então até a primeira execução é rápida.
Busca linear vs busca binária
A busca binária divide o intervalo pela metade a cada passo — muito menos verificações.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete countOccurrences(int[] a, int target) que retorna quantas vezes target aparece em a (uma varredura linear). Retorne 0 se nunca aparecer.
Clique em Executar para ver a saída aqui.