Qual a diferença de esforço entre busca linear e binária?

A linear examina até todos os itens, então o esforço acompanha o tamanho: dobrar a lista dobra o custo. A binária corta pela metade a cada passo, então dobrar a lista adiciona só um passo. Numa lista de um milhão, a linear pode fazer um milhão de comparações; a binária, cerca de vinte.

Por que a busca binária acha um item entre um milhão em cerca de vinte passos?

Porque cada passo corta as possibilidades pela metade. Um milhão dividido por dois, vinte vezes seguidas, chega a um. Como cada corte é um passo, vinte passos varrem um milhão de itens. É a mesma matemática de adivinhar um número de 1 a 100 em sete tentativas.

Então devo sempre usar busca binária?

Não. A binária exige dados ordenados e vale mais quando a lista é grande e você faz muitas buscas. Para listas pequenas, dados embaralhados ou poucas consultas, a busca linear é mais simples e não exige ordenar. A escolha depende da ordem dos dados e da quantidade de buscas.

E o dicionário e o conjunto, não buscam rápido também?

Buscam, e de forma instantânea, quando o acesso é por uma chave única, sem nem precisar de ordem. Se o seu caso é achar pelo identificador (nome, código), o dicionário ou o conjunto costumam ser ainda melhores. A busca binária brilha em listas ordenadas onde você procura por valor ou faixa.

Esse crescimento do esforço tem um nome?

Tem, e é o tema do próximo módulo, o de eficiência. A linear tem crescimento linear (acompanha o tamanho); a binária tem crescimento logarítmico (adiciona um passo quando o tamanho dobra). Você vai conhecer essa forma de medir e comparar o custo dos algoritmos, sem matemática pesada.

O que este módulo prepara para o resto do curso?

Duas coisas. Primeiro, a ordenação (próximo módulo): a busca binária exige dados ordenados, então é natural aprender a ordená-los. Segundo, a eficiência: o abismo entre linear e binária é um exemplo perfeito de por que medir o custo dos algoritmos importa. Busca, ordenação e eficiência formam um trio.

Módulo 10 - Busca: achar rápido

Linear ou binária: o abismo de esforço

8 min de leitura · por Cesar Gargiulo, revisado pela equipe ValorFinal e GuardiaSec · Atualizado em 08/07/2026

O que você vai aprender

Comparar o esforço da busca linear e da binária conforme o tamanho.
Perceber o abismo: crescimento em linha reta contra crescimento suave.
Escolher a busca certa considerando ordem e número de consultas.
Conectar o custo das buscas com a ideia de eficiência.

O abismo em números

A diferença entre as duas buscas fica pequena em listas curtas e vira um abismo em listas grandes, e é isso que torna a busca binária tão celebrada. A razão está em como o esforço de cada uma cresce com o tamanho. Na busca linear, o custo acompanha o tamanho em linha reta: se a lista dobra, o número máximo de comparações dobra. Na busca binária, cada passo corta o problema ao meio, então o custo cresce de forma incrivelmente lenta: dobrar o tamanho da lista adiciona apenas UM passo à busca. Deixe esse contraste afundar. Para achar um item, ir de mil para dois mil itens faz a busca linear trabalhar o dobro, e a binária trabalhar um passo a mais. É a diferença entre um custo que explode e um que quase não se mexe.

Tamanho da lista	Busca linear (pior caso)	Busca binária (pior caso)
100 itens	até 100 comparações	cerca de 7 comparações
10 mil itens	até 10 mil comparações	cerca de 14 comparações
1 milhão de itens	até 1 milhão de comparações	cerca de 20 comparações
1 bilhão de itens	até 1 bilhão de comparações	cerca de 30 comparações

Enquanto a linear cresce em linha reta, a binária mal se mexe. Um bilhão de itens: 30 passos bastam.

Por que cabe um milhão em vinte passos

De onde vêm esses vinte passos mágicos para um milhão de itens? Da conta de cortar pela metade repetidamente. Um milhão pela metade dá quinhentos mil; de novo, duzentos e cinquenta mil; e assim por diante. Quantas vezes dá para dividir um milhão por dois até sobrar um? Cerca de vinte vezes. Cada corte é um passo da busca binária, então cerca de vinte passos varrem um milhão de possibilidades. É a mesma razão pela qual você adivinha um número de 1 a 100 em sete tentativas: cem cortado pela metade sete vezes chega a um. Essa relação, em que multiplicar o tamanho por muito só adiciona uns poucos passos, tem nome na computação e ganha um módulo inteiro a seguir, o de eficiência. Por ora, guarde a imagem: cortar pela metade é um dos movimentos mais poderosos que um algoritmo pode fazer.

🎮 Jogo da aula

Qual busca usar?

Para cada situação, escolha a busca mais adequada considerando a ordem dos dados e o número de consultas.

A regra prática para escolher

Fechando o módulo, uma regra prática que resume tudo. Pergunte-se duas coisas: os dados estão (ou podem ficar) ordenados, e você vai buscar muitas vezes? Se a lista é pequena, ou os dados estão embaralhados e você fará poucas buscas, use a busca linear, simples e universal. Se a lista é grande, os dados já estão ordenados ou vale a pena ordená-los, e você fará muitas buscas, use a busca binária e colha a velocidade. E lembre da alternativa que apareceu antes no curso: quando o acesso é por uma etiqueta única, o dicionário e o conjunto oferecem busca instantânea sem nem precisar ordenar. O ponto maior deste módulo não é decorar algoritmos, é perceber que a forma como os dados estão organizados muda radicalmente o esforço para trabalhar com eles. Essa percepção é a ponte direta para os dois próximos módulos: ordenar os dados e medir a eficiência.

Teste rápido

Numa lista ordenada, você DOBRA o número de itens. Como muda o esforço no pior caso de cada busca?

Perguntas frequentes

Qual a diferença de esforço entre busca linear e binária?: A linear examina até todos os itens, então o esforço acompanha o tamanho: dobrar a lista dobra o custo. A binária corta pela metade a cada passo, então dobrar a lista adiciona só um passo. Numa lista de um milhão, a linear pode fazer um milhão de comparações; a binária, cerca de vinte.
Por que a busca binária acha um item entre um milhão em cerca de vinte passos?: Porque cada passo corta as possibilidades pela metade. Um milhão dividido por dois, vinte vezes seguidas, chega a um. Como cada corte é um passo, vinte passos varrem um milhão de itens. É a mesma matemática de adivinhar um número de 1 a 100 em sete tentativas.
Então devo sempre usar busca binária?: Não. A binária exige dados ordenados e vale mais quando a lista é grande e você faz muitas buscas. Para listas pequenas, dados embaralhados ou poucas consultas, a busca linear é mais simples e não exige ordenar. A escolha depende da ordem dos dados e da quantidade de buscas.
E o dicionário e o conjunto, não buscam rápido também?: Buscam, e de forma instantânea, quando o acesso é por uma chave única, sem nem precisar de ordem. Se o seu caso é achar pelo identificador (nome, código), o dicionário ou o conjunto costumam ser ainda melhores. A busca binária brilha em listas ordenadas onde você procura por valor ou faixa.
Esse crescimento do esforço tem um nome?: Tem, e é o tema do próximo módulo, o de eficiência. A linear tem crescimento linear (acompanha o tamanho); a binária tem crescimento logarítmico (adiciona um passo quando o tamanho dobra). Você vai conhecer essa forma de medir e comparar o custo dos algoritmos, sem matemática pesada.
O que este módulo prepara para o resto do curso?: Duas coisas. Primeiro, a ordenação (próximo módulo): a busca binária exige dados ordenados, então é natural aprender a ordená-los. Segundo, a eficiência: o abismo entre linear e binária é um exemplo perfeito de por que medir o custo dos algoritmos importa. Busca, ordenação e eficiência formam um trio.

Fontes

Seu progresso fica salvo neste aparelho. Assinantes sincronizam entre os aparelhos.

← Busca binária: cortar pela metade Concluir e avançar →