10
$\begingroup$

I heard several possible explanations, so I would like some trustable reference.

Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from the below explanation (1). Until now I thought/heard that it comes from explanation (2). I would feel bad both for letting the wrong thing in his thesis, as well as telling him to remove it if it might be right.

(1) Consider the search for an integer in the interval $[0,2^{n-1}]$. We can find it using $n$ questions by asking in step $i$ the $i^{th}$ binary digit of the number.

(2) If we have a search space with $2^n$ elements, we can find an unknown element by questions that repeatedly split the remaining part of the space in two.

And yes, I know that (2) can give the same algorithm as (1) but that's not the point here. (2) can be also applied for more general problems.

$\endgroup$
16
  • 1
    $\begingroup$ Also, please note that the question asks for references. Please don't answer saying that it's because of such-and-such a reason without giving a reliable source. $\endgroup$ – David Richerby May 18 '15 at 22:04
  • 1
    $\begingroup$ @DavidRicherby, No, curiosity is not sufficient motivation for demanding a "trustable" reference. Curiosity would be a sufficient motivation for asking "Why is binary search called binary search?", but it's not sufficient reason to demand a reference / reliable source, and it's not sufficient reason to say "don't answer with an explanation; I only want reliable sources". If the OP came across multiple conflicting explanations, then the OP should tell us about them in the question (note the Math.SE question did not lead to conflicting explanations). $\endgroup$ – D.W. May 18 '15 at 22:38
  • 3
    $\begingroup$ I think you should start with giving what explanations you have. We might have an idea about the trust they should get. And it might help if you gave your own, preferably precise, definition of what you call binary search, so that we can be sure to talk of the same concept, or alternatively give a reference to such a definition. $\endgroup$ – babou May 18 '15 at 22:39
  • 2
    $\begingroup$ Volume 3 of Knuth TAoCP, anyone? Mine is at the office ... $\endgroup$ – Hendrik Jan May 18 '15 at 22:49
  • 3
    $\begingroup$ Related: hsm.stackexchange.com/questions/2200/… $\endgroup$ – Kyle Jones May 24 '15 at 20:41
2
$\begingroup$

I tried to look up the Mauchly reference cited by Knuth but my library seems to have misplaced their copy.

In the meantime, consider the following early-ish citations for "binary search":

  • Halpern, Mark. "Variable-width tables with binary-search facility." Communications of the ACM 1.2 (1958): 1-4.

    The family of subroutines described in this report was designed to create, search and maintain tables which are to contain entries of different lengths, and yet be amenable to search by partition, or “binary” search.

  • Nagler, H. "An estimation of the relative efficiency of two internal sorting methods." Communications of the ACM 3.11 (1960): 618-620.

    This report concerns the IBM 705, models I and II. It is a study of the machine time required by two internal sorting methods, the conventional two-way merge, and a form of the binary search, which is due to D. Mordy, of the IBM Corporation.

  • Petersen, T. L. RE-ENTRY VEHICLE SYNTHESIS PROGRAM. No. STL/TR-60-0000-09103 (pdf link). TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

    The value of ${V_0}^*$ for which $g({V_0}^*) = 0$ must now be found. It is easily seen that $g(0) = K_3 - 1$ and $g(K_1) = -1$, so that the required value of ${V_0}^*$ lies between 0 and $K_1$ if $K_3>1$. A binary search is conducted for the root of $g({V_0}^*)$; the ${V_0}^*$ selected is that for which the absolute value of the difference between consecutive values of ${V_0}^*$ is less than $0.01$.

I'll note how the first 1958 citation uses quotation marks around "binary" but by the third citation in 1960, a binary search is mentioned without any further description or explanation. The allusion to "search by partition" would tend to suggest that explanation 2) is closer, but further verification is required.

$\endgroup$
1
$\begingroup$

Explanation (2) is a good explanation.

(2) is the better explanation of the two, because it applies generally to all uses of binary search, not just one specific instance. (1) is not an unreasonable way to think about it -- it's just not as general or complete as (2).

I don't think you need to feel obliged to require the student to correct this statement. It would not be embarrassing if a student gave explanation (1) in their thesis, so you don't need to feel bad. But if you want to teach them something, you can tell them about explanation (2) and about how binary search is more general and why the name "binary search" is reasonable for the general algorithm as well. But it's a minor point and not something that I would view as problematic or embarrassing if they left things as is.

$\endgroup$
1
  • $\begingroup$ no refs! seems more like a historical question :( $\endgroup$ – vzn May 21 '15 at 15:45
1
$\begingroup$

According to Wikipedia, binary search concerns the search in an array of sorted values.

The more general concept of divide and conquer search by repeatedly spliting the search space is called dichotomic search (literally: "that cuts in two"). The use of dichotomy may be considered in other contexts, as sonn as you have something to split. It is actually the first expression I learned (in high school, I think, and that was long ago), including in cases where you might want to call it binary.

Afaik, "dichotomic" does not imply that the two parts are (nearly) equal.

I do not know that binary is reserved to search in a space of size $2^n$.

Dichotomic is clearly the more general term, but it may sound pedantic to some who might instead improperly use binary.

Your example (1) is strangely stated, as one does not consciously ask for binary digits, but rather for comparison with the median of an interval. But it could qualify as binary.

Youe example (2) is unclear. Just splitting in two should be called dichotomic. Now, as you seem to hypothesize (strangely) a way of making 2 equal parts, I am not sure.

But a guessing game, where people ask questions that are answered by yes or no is clearly dichotomic.

My own guess, no reference given:

The original expression was probably "dichotomic", but with the popularity of binary systems, binary computer, etc., the term "binary" became more popular.

One other factor that may have played an important role is that binary search (as well as dichotomic) is based on binary choices. Now the expression "dichotomous choice" does exists, but is much less used than "binary choice", which appear about 6 times more often on the web.

So this may have influenced that. We should remember that though we are largely immersed in binary number (I mean we, computer scientist), most people are not and are nor concerned with binary numbers, but will easily talk of a binary choice. It is true that binary search is a topic for computer scientist, but short of a reliable reference to the contrary I will not believe it comes from binary numbers in any direct way.

$\endgroup$
3
  • $\begingroup$ "According to Wikipedia, binary search concerns the search in an array of sorted values." - Well, that's not how I read Wikipedia. If Wikipedia says it has to be in an array to count as binary search well, then, I think Wikipedia is debateable on this -- but the Wikipedia article doesn't seem to say that. Further down the Wikipedia article says that binary search "allows searching over argument of any monotonic function for a point, at which function reaches the arbitrary value" -- which is not search in an array. $\endgroup$ – D.W. May 21 '15 at 20:49
  • $\begingroup$ "The more general concept of divide and conquer search by repeatedly spliting the search space is called dichotomic search" - That doesn't match my own experience. I routinely hear this called binary search. $\endgroup$ – D.W. May 21 '15 at 20:51
  • $\begingroup$ @D.W. As I told you before, my memory is not much to be trusted. But binary search, or even divide and conquer are algorithmic terminology that came to us with computers. But I think there were not many computers around when I first heard of dichotomic search, Then a good printed reference would be a lot better than my (f)ailing memory. Regarding wikipedia, I did not read the whole article. Basically I did not think I would get a definitive answer ... and I have some doubt there is one. The idea is general, the terminology nice, and must have been adapted by each to whatever problem at hand. $\endgroup$ – babou May 21 '15 at 20:58
1
$\begingroup$

Knuth (V.3 Pg. 82) gives Mauchly as the source for binary search; it is used to find the insertion point during a sort which then shuffles elements forward to make a vacancy, in a process called binary insertion.

So (2) would be valid, but I can't see the original paper; it's obscured here: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.