Diferença entre pesquisa binária e pesquisa linear

Pesquisa binária vs Pesquisa linear

A pesquisa linear, também conhecida como pesquisa seqüencial, é o algoritmo de pesquisa mais simples. Ele procura por um valor especificado em uma lista, verificando todos os elementos da 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 especificado na lista.

O que é pesquisa linear?

A 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, coleção ou sequência) e o item que precisa ser pesquisado. A saída será verdadeira 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 percorre todos os elementos da lista antes de encontrar o elemento necessário. A complexidade da pesquisa 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?

A pesquisa binária também é um método usado para localizar um item especificado em uma lista classificada. Este 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 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 exclusivo indicando isso. Portanto, o método de pesquisa binária reduz pela metade o número de elementos comparados (em cada iteração), dependendo do resultado da comparação. Conseqüentemente, a pesquisa binária é executada em tempo logarítmico, resultando em o (log n) desempenho médio dos casos.

Qual é a diferença entre Pesquisa Binária e Pesquisa Linear?

Mesmo que a pesquisa linear e a pesquisa binária estejam pesquisando métodos, elas têm várias diferenças. Enquanto a pesquisa binária opera em listas classificadas, a pesquisa de linha também pode operar em listas não classificadas. A classificação de uma lista geralmente tem uma complexidade média de caso de n log n. A pesquisa linear é simples e direta de implementar do que a pesquisa binária. Porém, a pesquisa linear é muito lenta para ser usada com grandes listas devido ao seu (n) desempenho médio de casos. Por outro lado, a pesquisa binária é considerada um método mais eficiente que pode ser usado com grandes listas. Mas implementar a pesquisa binária pode ser bastante complicado e um estudo mostrou que o código exato da pesquisa binária pode ser encontrado em apenas cinco dos vinte livros.