Por que a pesquisa binária é chamada de pesquisa binária?

Ouvi várias explicações possíveis, então gostaria de alguma referência confiável.

Atualização 05.19: Estou interessado na pergunta, porque um dos meus alunos escreveu em sua tese que o nome vem da explicação abaixo (1). Até agora, pensei / ouvi dizer que se trata de uma explicação (2). Eu me sentiria mal por deixar a coisa errada em sua tese, bem como dizer a ele para removê-la, se possível.

(1) Considere a busca de um número inteiro no intervalo . Podemos encontrá-lo usando perguntas, perguntando na etapa o dígito binário do número.n i i t $[0,2^{n-1}]$$n$$i$$i^{th}$

(2) Se tivermos um espaço de pesquisa com elementos, podemos encontrar um elemento desconhecido por perguntas que dividem repetidamente a parte restante do espaço em duas .$2^n$

E sim, eu sei que (2) pode dar o mesmo algoritmo que (1), mas esse não é o ponto aqui. (2) também pode ser aplicado para problemas mais gerais.

A explicação (2) é uma boa explicação.

(2) é a melhor explicação dos dois, porque se aplica geralmente a todos os usos da pesquisa binária, não apenas a uma instância específica. (1) não é uma maneira irracional de pensar sobre isso - simplesmente não é tão geral ou completa quanto (2).

Não acho que você precise se sentir obrigado a exigir que o aluno corrija essa afirmação. Não seria embaraçoso se um aluno desse uma explicação (1) em sua tese, para que você não precise se sentir mal. Mas se você quiser ensinar alguma coisa a eles, pode contar sobre a explicação (2) e sobre como a pesquisa binária é mais geral e por que o nome "pesquisa binária" também é razoável para o algoritmo geral. Mas é um ponto menor e não algo que eu consideraria problemático ou embaraçoso se eles deixassem as coisas como estão.

Segundo a Wikipedia, a pesquisa binária diz respeito à pesquisa em uma matriz de valores classificados.

O conceito mais geral de dividir e conquistar a pesquisa dividindo repetidamente o espaço de pesquisa é chamado de pesquisa dicotômica (literalmente: "que se divide em dois"). O uso da dicotomia pode ser considerado em outros contextos, por mais que você tenha algo a dividir. Na verdade, é a primeira expressão que aprendi (no ensino médio, acho, e isso foi há muito tempo), inclusive nos casos em que você pode chamá-lo de binário.

Afaik, "dicotômica" não implica que as duas partes sejam (quase) iguais.

Não sei se o binário está reservado para pesquisar em um espaço de tamanho .$2^n$

Dicotômica é claramente o termo mais geral, mas pode soar pedante para alguns que poderiam usar o binário de forma inadequada.

Seu exemplo (1) é estranhamente declarado, pois não se solicita conscientemente dígitos binários, mas sim uma comparação com a mediana de um intervalo. Mas poderia se qualificar como binário.

Seu exemplo (2) não é claro. Apenas dividir em dois deve ser chamado de dicotômico. Agora, como você parece sugerir (estranhamente) uma maneira de fazer duas partes iguais, não tenho certeza.

Mas um jogo de adivinhação, no qual as pessoas fazem perguntas que são respondidas com sim ou não, é claramente dicotômico.

Meu palpite, nenhuma referência dada:

A expressão original era provavelmente "dicotômica", mas com a popularidade de sistemas binários, computadores binários etc., o termo "binário" se tornou mais popular.

Um outro fator que pode ter desempenhado um papel importante é que a pesquisa binária (assim como a dicotômica) se baseia em escolhas binárias. Agora, a expressão " escolha dicotômica " existe, mas é muito menos usada do que " escolha binária ", que aparece cerca de 6 vezes mais frequentemente na web.

Então, isso pode ter influenciado isso. Devemos lembrar que, embora estejamos imersos em grande número em número binário (quero dizer, nós, cientistas da computação), a maioria das pessoas não está nem se preocupa com números binários, mas fala facilmente de uma escolha binária. É verdade que a pesquisa binária é um tópico para o cientista da computação, mas, sem uma referência confiável ao contrário, não acreditarei que ela venha de números binários de maneira direta.

Knuth (V.3, pág. 82) fornece Mauchly como fonte de pesquisa binária; é usado para encontrar o ponto de inserção durante uma classificação que embaralha elementos para a frente para criar uma vaga, em um processo chamado inserção binária.

Então (2) seria válido, mas não consigo ver o artigo original; está obscurecido aqui: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating

Tentei procurar a referência de Mauchly citada por Knuth, mas minha biblioteca parece ter extraviado a cópia deles.

Enquanto isso, considere as seguintes citações iniciais para "pesquisa binária":

• Halpern, Mark. " Tabelas de largura variável com recurso de pesquisa binária. " Communications of the ACM 1.2 (1958): 1-4.

  A família de sub-rotinas descritas neste relatório foi projetada para criar, pesquisar e manter tabelas que devem conter entradas de diferentes comprimentos e, ainda assim, facilitar a pesquisa por partição ou pesquisa "binária".

• Nagler, H. " Uma estimativa da eficiência relativa de dois métodos de classificação internos. " Communications of the ACM 3.11 (1960): 618-620.

  Este relatório refere-se ao IBM 705, modelos I e II. É um estudo do tempo da máquina exigido por dois métodos de classificação internos, a mesclagem bidirecional convencional e uma forma de pesquisa binária, devida a D. Mordy, da IBM Corporation.

• Petersen, TL PROGRAMA DE SÍNTESE DO VEÍCULO DE RE-ENTRADA. No. STL / TR-60-0000-09103 (link em pdf) . A TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

  O valor de para o qual agora deve ser encontrado . É facilmente visto que o e , de modo que o valor necessário de situa-se entre 0 e se . Uma pesquisa binária é conduzida para a raiz de ; o selecionado é aquele para o qual o valor absoluto da diferença entre os valores consecutivos de é menor que .g( V 0 ∗)=0g(0)=K3-1g(K1)=-1 V 0 ∗K1K3>1g( V 0 ∗) V 0 ∗ V 0 ∗${V_0}^*$$g({V_0}^*) = 0$$g(0) = K_3 - 1$$g(K_1) = -1$${V_0}^*$$K_1$$K_3>1$$g({V_0}^*)$${V_0}^*$${V_0}^*$$0.01$

Observarei como a primeira citação de 1958 usa aspas em torno de "binário", mas na terceira citação em 1960, uma pesquisa binária é mencionada sem nenhuma descrição ou explicação adicional. A alusão à "pesquisa por partição" tenderia a sugerir que a explicação 2) está mais próxima, mas é necessária uma verificação adicional.