11
$\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.

Improve this question
$\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
    Commented May 18, 2015 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. ♦
    Commented May 18, 2015 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
    Commented May 18, 2015 at 22:39
  • 2
    $\begingroup$ Volume 3 of Knuth TAoCP, anyone? Mine is at the office ... $\endgroup$
    – Hendrik Jan
    Commented May 18, 2015 at 22:49
  • 3
    $\begingroup$ Related: hsm.stackexchange.com/questions/2200/… $\endgroup$
    – Kyle Jones
    Commented May 24, 2015 at 20:41

4 Answers 4

Reset to default
3
$\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":

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.

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.

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.

EDITED TO ADD:

It turns out that the Internet Archive has a copy of the 1946 Mauchly reference in a 1985 reprinting of the Moore Lectures and, well, there's a little bit of a surprise in there:

It is obviously desirable, however, to have the tabular arguments arranged in a sequence of ascending or descending values, and this is customarily done. A human computer in referring to a table makes use of this orderly arrangement and does not examine every entry in the table in order to discover the one in which he is interested. A computing machine can perform the same kind of a process automatically in various ways, one of which we may describe as follows. Let us think of the table as subdivided in binary fashion first into halves, then into quarters, eighths, etc. The machine can then determine whether the desired argument value lies in the first half or the second half of the table. Next it will determine which quarter of the chosen half contains the desired argument. It proceeds further to locate the particular eighth of the table, then the particular sixteenth part of the table etc.

We see that by this process a considerable acceleration over the serial scanning can be obtained. [...] On the other hand the binary process just described requires only $\mbox{log}_2n$ comparisons to arrive at the desired value [...]

If a binary system is used for representing numbers within the machine, the binary process just described can be carried out in a simple way. Essentially the machine must first look at the first binary digit of the desired argument to select which half of the table it will lie in, and the determination of the further subdivisions of the table all correspond to successive binary digits of the argument number.

So, while the binary process described matches the partitioning-into-halves explanation, Mauchly immediately also alludes to a bitwise interpretation, though it seems slightly different from the interpretation in the original question.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ no refs! seems more like a historical question :( $\endgroup$
    – vzn
    Commented May 21, 2015 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.

Improve this answer
$\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. ♦
    Commented May 21, 2015 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. ♦
    Commented May 21, 2015 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
    Commented May 21, 2015 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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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