Searching: linear and binary
Duas formas de buscar
- Buscar significa encontrar onde um valor está em uma matriz (ou dizer que não existe).
- Busca linear verifica cada item um por um. Funciona em qualquer matriz.
- Busca binária é muito mais rápida, mas precisa que a matriz esteja ordenada antes.
Busca linear
- Percorra do índice
0atén - 1, comparando cada item com o alvo. - Retorne o índice no momento em que encontrar. Se chegar ao final, retorne
-1. - Para uma matriz de
nitens, isso verifica aténdeles.
Por que ordenação habilita busca binária
- Se a matriz estiver ordenada, você pode pular para o meio e comparar.
- Se o meio for muito pequeno, o alvo deve estar na metade direita; se muito grande, na esquerda.
- Cada passo descarta metade da matriz, então é muito rápido (cerca de
log2(n)passos).
low, high, mid
- Mantenha dois limites:
low(início) ehigh(fim). O meio émid = low + (high - low) / 2. - Se
a[mid]for o alvo, retornemid. Se fora[mid] < target, movalow = mid + 1; caso contrário, movahigh = mid - 1. - Pare quando
low > high— o alvo não está lá, então retorne-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
Erros comuns
- A busca binária precisa de um array ordenado.
- Busca linear verifica cada elemento em sequência.
Agora você tenta
- Para busca binária, assuma que a matriz já está ordenada. Use
low,highemid. - Retorne
-1quando o valor não for encontrado. Não escreva ummain— o verificador fornece um.
Busca linear vs busca binária
Binary search halves the range each step.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do não write a main.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do não write a main.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do não write a main.
Clique em Executar para ver a saída aqui.