Pesquisa Binária vs Pesquisa Linear
A busca linear, também conhecida como busca sequencial, é o algoritmo de busca mais simples. Ele procura um valor especificado em uma lista verificando cada elemento na lista. A pesquisa binária também é um método usado para localizar um valor especificado em uma lista classificada. O método de pesquisa binária reduz pela metade o número de elementos verificados (em cada iteração), reduzindo o tempo necessário para localizar o item fornecido na lista.
O que é Pesquisa Linear?
Pesquisa linear é o método de pesquisa mais simples, que verifica cada elemento em uma lista sequencialmente até encontrar um elemento especificado. A entrada para o método de pesquisa linear é uma sequência (como uma matriz, uma coleção ou uma string) e o item que precisa ser pesquisado. A saída será true se o item especificado estiver dentro da sequência fornecida ou false se não estiver na sequência. Como esse método verifica todos os itens da lista até que o item especificado seja encontrado, na pior das hipóteses ele passará por todos os elementos da lista antes de encontrar o elemento necessário. A complexidade da busca linear é o(n). Portanto, é considerado muito lento para ser usado ao pesquisar elementos em grandes listas. Mas isso é muito simples e fácil de implementar.
O que é Pesquisa Binária?
Busca binária também é um método usado para localizar um item especificado em uma lista ordenada. Esse método começa comparando o elemento pesquisado com os elementos no meio da lista. Se a comparação determinar que os dois elementos são iguais, o método para e retorna a posição do elemento. Se o elemento pesquisado for maior que o elemento do meio, ele inicia o método novamente usando apenas a metade inferior da lista classificada. Se o elemento pesquisado for menor que o elemento do meio, ele inicia o método novamente usando apenas a metade superior da lista classificada. Se o elemento pesquisado não estiver na lista, o método retornará um valor único indicando isso. Portanto, o método de busca binária reduz pela metade o número de elementos comparados (em cada iteração), dependendo do resultado da comparação. Consequentemente, a pesquisa binária é executada em tempo logarítmico, resultando em o(log n) desempenho médio do caso.
Qual é a diferença entre Pesquisa Binária e Pesquisa Linear?
Mesmo que tanto a busca linear quanto a busca binária sejam métodos de busca, eles têm várias diferenças. Enquanto a pesquisa binária opera em listas classificadas, a pesquisa linear também pode operar em listas não classificadas. A ordenação de uma lista geralmente tem uma complexidade de caso média de n log n. a busca linear é simples e direta de implementar do que a busca binária. Mas, a pesquisa linear é muito lenta para ser usada com listas grandes devido ao seu desempenho de caso o(n) médio. Por outro lado, a busca binária é considerada um método mais eficiente que pode ser usado com listas grandes. Mas implementar a pesquisa binária pode ser bastante complicado e um estudo mostrou que o código preciso para a pesquisa binária pode ser encontrado em apenas cinco dos vinte livros.
