Pesquisa binária

Question

Então, quero entender mais sobre a pesquisa binária, porque eu realmente não entendo. A pesquisa binária requer uma pré -condição de que uma matriz seja classificada. Eu entendi certo? Parece que um método deve verificar essa pré -condição e lançar uma exceção se não for atendida. Mas, por que verificar a pré -condição está uma má ideia?

Answer 1

É uma má ideia porque verificar os dados são classificados n degraus. Toda a pesquisa é sobre log(n) degraus.
Se você vai verificar, é melhor fazer uma pesquisa linear.

Answer 2

O objetivo de uma pesquisa binária é que, como os dados já estão classificados, você pode localizar rapidamente as informações desejadas.

Pegue a lista telefônica, que é classificada pelo sobrenome.

Como você encontra alguém na lista telefônica? Você o abre para uma página que você assume estar perto do que deseja e, em seguida, inicia as páginas.

Mas você não vira uma página a cada vez, se você perdeu muita coisa, vira um monte de páginas e, finalmente, começa a lançar um de cada vez, até que finalmente você comece a olhar para uma única página.

É isso que a pesquisa binária faz. Como os dados são classificados, ele sabe que pode pular muito e fazer outra aparência, e se concentrará nas informações desejadas.

Uma pesquisa binária faz 1 comparação para cada número duplicado de itens. Portanto, uma coleção de 1024 elementos exigiria cerca de 10 comparações, no máximo, para encontrar suas informações ou pelo menos descobrir que elas não estão lá.

Se você, antes de executar a pesquisa binária real, fizer uma execução completa para verificar se os dados são classificados, é melhor fazer uma varredura para obter as informações. Uma execução completa + a pesquisa binária exigirá operações N + LOG2 N; portanto, para 1024 elementos, seria necessário cerca de 1034 comparações, enquanto uma varredura simples para as informações exigirá em média metade, que é 512.

Portanto, se você não pode garantir que os dados sejam classificados, não deve usar a pesquisa binária, pois serão superados por uma digitalização simples.

---

Editar: Eu direi isso, porém, você pode adicionar uma etapa de código somente de depuração para verificar isso, para capturar bugs no código que deve preparar os dados para pesquisa binária, mas saiba que, devido ao que escrevi acima, Isso tornará o tempo total de execução muito mais alto; portanto, dependendo do que você deseja fazer com essa verificação, você pode ou não querer adicioná -la. Mas não deve estar presente no código de liberação.

Answer 3

Sim, uma pesquisa binária envolve 0 (log n) etapas e a verificação de toda a sequência é classificada envolve 0 (n) etapas. Do meu ponto de vista, é bom verificá -lo no modo de depuração, não durante a liberação.

Answer 4

Pesquisa binária pressupõe que os dados de entrada sejam classificados. Então aqui você está correto.

Agora, em geral, a verificação se os dados forem classificados em algum momento. Portanto, executar isso antes de cada pesquisa tornaria a pesquisa realmente ineficiente.

Mais detalhes.

Suponha que 'n' seja a quantidade de seus dados.

Pesquisa binária precisa O(log(n)) Operação no pior caso, para encontrar um elemento. Certificando -se de que os dados sejam classificados requer O(n) operações.

Então, se verificarmos a pré -condição todas as vezes para muito grande n Começaremos a gastar a maior parte do tempo verificando a pré -condição do que fazer pesquisas reais.

E não é tão difícil dizer quando você verá esse efeito. Acabei de calcular quanto tempo você gastará em pré-cheque versus pesquisa real

• Para 1 elemento, você não gasta tempo pesquisando.
• Para 2 elementos, você gasta 50% na pesquisa.
• Para 5 elementos, você gasta 46% na pesquisa
• Para 20 elementos, você gasta 22% na pesquisa.
• Para 100 elementos, você gasta 7% na pesquisa.

E assim por diante. Em todos os casos, o descanso no tempo é gasto em verificação de pré -condição.

Answer 5

Além do que todos os outros disseram sobre o tempo de execução (o (n) para verificar todos os itens, vs. O (log (n)) para executar a pesquisa binária.)

Eu acho que você está entendendo mal a idéia de uma pré-condição. Pré-condições e pós-condições são um contrato. Se sua pré -condição for verdadeira e você executa seu algoritmo, sua condição de postagem será verdadeira. Se sua pré -condição for falsa, você não garantirá a condição da postagem.

Então, basicamente, a pesquisa binária diz o seguinte: se os dados que você me fornecem já estiver classificado, posso dizer a posição de uma peça de dados específica ou se não estiver presente, executando verificações de log (n). Se os dados não forem classificados, não tenho garantias sobre minha resposta.

O trabalho que leva você da sua pré-condição para a sua condição, se o seu algoritmo. Nesse caso, pesquisa binária.

Answer 6

A pergunta original pressupõe que você esteja usando uma pesquisa binária em uma coleção de dados. Esse não é sempre o caso. Muitas vezes você está apenas tentando calcular um número em algum intervalo.

Suponha que você esteja tentando calcular a configuração de velocidade ideal para um ventilador. Por algum motivo, você não pode encontrar uma expressão de forma fechada, então simula o fluxo de ar em diferentes configurações de velocidade.

Supondo que o ventilador possa funcionar a qualquer velocidade de 0rpm a 5000rpm, você não precisa gerar uma lista de velocidades possíveis. Você apenas encontra a média do mínimo e o máximo anterior em cada etapa da pesquisa binária.