Why is binary search called binary search?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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