Diferença Entre Pesquisa Binária E Pesquisa Linear

2024 Autor: Mildred Bawerman | [email protected]. Última modificação: 2023-12-16 08:41

Pesquisa Binária vs Pesquisa Linear

A pesquisa linear, também conhecida como pesquisa sequencial, é o algoritmo de pesquisa 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 divide 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?

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 um array, coleção ou string) e o item que precisa ser pesquisado. A saída é verdadeira se o item especificado estiver na sequência fornecida ou falso 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 listas grandes. 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 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 pesquisa binária divide 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?

Embora a pesquisa linear e a pesquisa binária sejam métodos de pesquisa, elas 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. Classificar 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. Mas, a pesquisa linear é muito lenta para ser usada com listas grandes devido ao seu desempenho de caso médio o (n). Por outro lado, a pesquisa 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.