Pesquisa linear vs. binária
Pesquisa linear vs. binária é um experimento interativo de Algoritmos em ação, uma simulação gratuita do StudyFi Lab que funciona direto no navegador.
A pesquisa linear verifica os elementos um a um, por isso no pior caso precisa de n passos — O(n). A pesquisa binária só funciona num vetor ordenado: olha para o meio e, conforme o resultado, descarta uma metade inteira. Depois de cada passo resta no máximo metade, por isso bastam no máximo ⌈log₂(n+1)⌉ passos — O(log n). Para 40 elementos são 6 passos em vez de 40.
Experimente: Define 40 elementos e procura o último valor. Depois escolhe um número que não está no vetor — quantos passos precisa cada pesquisa para o descobrir?
Perguntas frequentes
O que mostra o experimento “Pesquisa linear vs. binária”?
A pesquisa linear verifica os elementos um a um, por isso no pior caso precisa de n passos — O(n). A pesquisa binária só funciona num vetor ordenado: olha para o meio e, conforme o resultado, descarta uma metade inteira. Depois de cada passo resta no máximo metade, por isso bastam no máximo ⌈log₂(n+1)⌉ passos — O(log n). Para 40 elementos são 6 passos em vez de 40.
Como experimento “Pesquisa linear vs. binária”?
Define 40 elementos e procura o último valor. Depois escolhe um número que não está no vetor — quantos passos precisa cada pesquisa para o descobrir?
Estudando para uma prova?
Envie suas anotações e o StudyFi as transforma em flashcards, testes e podcasts.