Busca linear
A ideia
Seção intitulada “A ideia”Você perdeu a chave numa fileira de gavetas. Sem nenhuma pista, o único jeito garantido é abrir uma gaveta de cada vez, da primeira até a última, até achar.
Essa é a busca linear: percorrer os elementos em ordem e comparar cada um com o alvo. Ela funciona com qualquer array, ordenado ou não.
Veja rodando
Seção intitulada “Veja rodando”Clique em ▶ ou avance um passo de cada vez. Acompanhe a linha destacada no código e o valor de i.
Vamos procurar 25 olhando um elemento de cada vez, da esquerda para a direita.
function linearSearch(array: number[], target: number): number {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i
}
}
return -1
}- target
- 25
Agora você prevê
Seção intitulada “Agora você prevê”Neste array o alvo não existe. Antes de cada passo, clique no índice que a busca vai examinar. Quando achar que ela vai parar, escolha Nenhum.
Vamos procurar 6 olhando um elemento de cada vez, da esquerda para a direita.
function linearSearch(array: number[], target: number): number {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i
}
}
return -1
}- target
- 6
| Caso | Comparações | Quando acontece |
|---|---|---|
| Melhor | 1 | O alvo é o primeiro elemento |
| Pior | n | O alvo é o último ou não existe |
| Médio | ~n/2 | O alvo está numa posição aleatória |
O tempo cresce na mesma proporção que o array: O(n). A memória extra é só a variável i: O(1).
Onde você já usa
Seção intitulada “Onde você já usa”Em JavaScript, Array.prototype.indexOf, includes, find e findIndex fazem busca linear. Elas são ótimas para arrays pequenos ou quando você vai procurar uma vez só. Se vai procurar muitas vezes no mesmo array grande, um Set ou um Map (busca em O(1) na média) ou um array ordenado com busca binária costumam valer a pena.
Teste sua memória
Seção intitulada “Teste sua memória”Responda sem rolar a página para cima.
Pronto para praticar? Comece pelo tesouro do pirata.