patternMinor
Why is binary search called binary search?
Viewed 0 times
whycalledbinarysearch
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#42726, answer score: 2
Revisions (0)
No revisions yet.