Binary search - Revision history

162.158.46.6: Changed last letter from 'm' to 'r' in the case 1 of proof of correctness.

2017-03-19T05:17:40Z

Changed last letter from 'm' to 'r' in the case 1 of proof of correctness.

162.158.46.24: /* Implementation */

2017-01-01T04:59:12Z

‎Implementation

Brian: removed Category:Incomplete

2012-02-11T23:45:27Z

removed Category:Incomplete

Brian at 23:44, 11 February 2012

2012-02-11T23:44:20Z

Brian at 21:36, 11 February 2012

2012-02-11T21:36:25Z

Brian at 08:47, 1 January 2012

2012-01-01T08:47:48Z

Brian: /* Possible bugs */

2012-01-01T08:14:27Z

‎Possible bugs

Brian: Created page with "'''Binary search''' is the term used in computer science for the discrete version of the ''bisection method'', in which given a monotone function $f$ over a discrete i..."

2012-01-01T08:04:54Z

Created page with "'''Binary search''' is the term used in computer science for the discrete version of the ''bisection method'', in which given a monotone function <math>f</math> over a discrete i..."

New page

'''Binary search''' is the term used in computer science for the discrete version of the ''bisection method'', in which given a monotone function <math>f</math> over a discrete interval <math>I</math> and a target value <math>c</math> one wishes to find <math>x \in I</math> for which <math>f(x) \approx c</math>. It is most often used to locate a value in a sorted [[array]]. The term may also be used for the continuous version.

==Discrete: array==
In the most commonly encountered variation of binary search, we are given a zero-indexed [[array]] <math>A</math> of size <math>n</math> that is sorted in ascending order, along with some value <math>c</math>. Here the domain of the function <math>f</math> is the set of indices into the array, and <math>f(i) = A_i</math> where <math>A_i</math> is the element at the <math>i</math><sup>th</sup> position. There are two slightly different variations on what we wish to do:
* ''Lower bound'': Here are two equivalent formulations:
:# Find the ''first'' index into <math>A</math> where we could insert a new element of value <math>c</math> without violating the ascending order.
:# If there is an element in <math>A</math> with value greater than ''or equal to'' <math>c</math>, return the index of the first such element; otherwise, return <math>n</math>. In other words, return <math>\min\{i\,|\,A_i \geq c\}</math>, or <math>n</math> if that set is empty.
* ''Upper bound'':
:# Find the ''last'' index into <math>A</math> where we could insert a new element of value <math>c</math> without violating the ascending order.
:# If there is an element in <math>A</math> with value ''strictly'' greater than to <math>c</math>, return the index of the first such element; otherwise, return <math>n</math>. In other words, return <math>\min\{i\,|\,A_i > c\}</math>, or <math>n</math> if that set is empty.
The following properties then hold:
* If there is no <math>i</math> such that <math>A_i = c</math>, then the lower bound and upper bound will be the same; they will both point to the first element in <math>A</math> that is greater than <math>c</math>.
:* If <math>c</math> is larger than all elements in <math>A</math>, then the lower and upper bounds will both be <math>n</math>.
* If there is at least one element <math>A</math> with value <math>c</math>, then the lower bound will be the index of the ''first'' such element, and the upper bound will be the index of the element ''just after the last'' such element. Hence [lower bound, upper bound) is a [[half-open interval]] that represents the range of indices into <math>A</math> that refer to elements with value <math>c</math>.
* The element immediately preceding the lower bound is the last element with value less than <math>c</math>, if this exists, or the hypothetical element at index -1, otherwise.
* The element immediately preceding the upper bound is the last element with value less than or equal to <math>c</math>, if this exists, or the hypothetical element at index -1, otherwise.

Both lower bound and upper bound can easily be found by iterating through the array from beginning to end, which takes <math>O(n)</math> comparisons and hence <math>O(n)</math> time if the elements of the array are simple scalar variables that take <math>O(1)</math> time to compare. However, because the array is sorted, we can do better than this. We begin with the knowledge that the element we seek might be anywhere in the array, or it could be "just past the end". Now, examine an element near the centre of the array. If this is less than the element we seek, we know the element we seek must be in the second half of the array. If it is greater, we know the element we seek must be in the first half. Thus, by making one comparison, we cut the range under consideration into half. It follows that after <math>O(\log n)</math> comparisons, we will be able to locate either the upper bound or the lower bound as we desire.

===Implementation===
However, implementation tends to be tricky, and even experienced programmers can introduce bugs when writing binary search. Correct reference implementations are given below in C:
<syntaxhighlight lang="c">
/* n is the size of the int[] array A. */
int lower_bound(int A[], int n, int c)
{
int l = 0;
int r = n;
while (l < r)
{
int m = (l+r)/2; /* Rounds toward zero. */
if (A[m] < c)
l = m+1;
else
r = m;
}
return l;
}

int upper_bound(int A[], int n, int c)
{
int l = 0;
int r = n;
while (l < r)
{
int m = (l+r)/2;
if (A[m] <= c) /* Note use of < instead of <=. */
l = m+1;
else
r = m;
}
return l;
}
</syntaxhighlight>

===Proof of correctness===
We prove that <code>lower_bound</code> above is correct. The proof for <code>upper_bound</code> is very similar.

We claim the invariant that, immediately before and after each iteration of the <code>while</code> loop:
# The index we are seeking is at least <code>l</code>.
# The index we are seeking is at most <code>r</code>.
This is certainly true immediately before the first iteration of the loop, where <code>l = 0</code> and <code>r = n</code>. Now we claim that if it is true before a given iteration of the loop, it will be true after that iteration, which, by induction, implies our claim. First, the value <code>m</code> will be exactly the arithmetic mean of <code>l</code> and <code>r</code>, if their sum is even, or it will be 0.5 less than the mean, if their sum is odd, since <code>m</code> is computed as the arithmetic mean rounded down. This implies that, in any given iteration of the loop, <code>m</code>'s initial value will be at least <code>l</code>, and strictly less than <code>r</code>. Now:
* ''Case 1'': <code>A[m] < c</code>. This means that no element with index between <code>l</code> and <code>m</code>, inclusive, can be greater than <code>c</code>, because the array is sorted. But because we know that such an element exists (or that it is the hypothetical element just past the end of the array) in the current range delineated by indices <code>l</code> and <code>r</code>, we conclude that it must be in the second half of the range with indices from <code>m+1</code> to <code>r</code>, inclusive. In this case we set <code>l = m+1</code> and at the end of the loop the invariant is again satisfied. This is guaranteed to increase the value of <code>l</code>, since <code>m</code> starts out with value at least <code>l</code>. It also does not increase <code>l</code> beyond <code>r</code>, since <code>m</code> is initially strictly less than <code>m</code>.
* ''Case 2'': <code>A[m] >= c</code>. This means that there exists an element with index between <code>l</code> and <code>m</code>, inclusive, which is at least <code>c</code>. This implies that the first such element is somewhere in this half of the range, because the array is sorted. Therefore, after setting <code>r = m</code>, the range of indices between <code>l</code> and <code>r</code>, inclusive, will still contain the index we are seeking, and hence the invariant is again satisfied. This is guaranteed to decrease the value of <code>r</code>, since <code>m</code> starts out strictly less than <code>r</code>; it also will not decrease it beyond <code>l</code>, since <code>m</code> starts out at least as large as <code>l</code>.
Since each iteration of the loop either increases <code>l</code> or decreases <code>r</code>, the loop will eventually terminate with <code>l = r</code>. Since the invariant still holds, this unique common value must be the solution. <math>_{\blacksquare}</math>

Carefully proving the <math>O(\log n)</math> time bound and showing the correctness of <code>upper_bound</code> are left as exercises to the reader.

===Possible bugs===
One obvious bug is absentmindedly setting <code>r = n-1</code> initially. Doing this will prevent the value <code>n</code> from ever being returned, which renders the implementation correct whenever the answer is less than <code>n</code>, but incorrect whenever it is <code>n</code>. (It will simply return <code>n-1</code> in this case.)

Another obvious bug is using <code>while (l <= r)</code> instead of <code>while (l < r)</code>. This will always cause an infinite loop in which the <code>else</code> branch is taken in every subsequent iteration.

A third obvious bug is either comparing <code>A[m]</code> with <code>c</code> in the wrong direction, that is, writing <code>A[m] > c</code>, <code>A[m] >= c</code>, <code>c < A[m]</code>, or <code>c <= A[m]</code>, or reversing the order of the two branches. This would not correspond to the theory, and would almost always given an incorrect result.

However, there are still four degrees of freedom in the implementation:
# Should we compare <code>A[m]</code> with <code>c</code> strictly, that is, with <code><</code>, or non-strictly, that is, with <code><=</code>?
# Should we compute <code>m</code> as the floor of the arithmetic mean of <code>l</code> and <code>r</code>, or as the ceiling?
# Should we set <code>l = m+1</code>, <code>l = m</code>, or <code>l = m-1</code> in the first branch?
# Should we set <code>r = m+1</code>, <code>r = m</code>, or <code>r = m-1</code> in the second branch?
These variations are covered in the page [[Binary search/Implementation details]].

← Older revision		Revision as of 23:45, 11 February 2012
Line 136:		Line 136:
	* {{SPOJ\|GLASNICI\|Glasnici @ SPOJ}}		* {{SPOJ\|GLASNICI\|Glasnici @ SPOJ}}
	* {{SPOJ\|PIE\|Pie @ SPOJ}}		* {{SPOJ\|PIE\|Pie @ SPOJ}}
−
−	~~[[Category:Incomplete]]~~

@@ Line 108: / Line 108: @@
 More generally, binary search is often very useful for problems that read something like "find the maximum <math>x</math> such that <math>P(x)</math>". For example, in {{Problem|ccc03s5|Trucking Troubles}}, the problem essentially down to finding the maximum <math>x</math> such that the edges of the given graph of weight at least <math>x</math> span the graph. This problem can be solved using [[Prim's algorithm]] to construct the "maximum spanning tree" (really, the minimum spanning tree using negated edge weights), but binary search provides a simpler approach. We know that <math>x</math> is somewhere in between the smallest edge weight in the graph and the largest edge weight in the graph, so we start by guessing a value roughly halfway in-between. Then we use [[depth-first search]] to test whether the graph is connected using only the edges of weight greater than or equal to our guess value. If it is, then the true value of <math>x</math> is greater than or equal to our guess; if not, then it is less. This is then repeated as many times as necessary to determine the correct value of <math>x</math>.
 ==Continuous==
-TODO
+The continuous version of the problem is like the number guessing game applied to real numbers: Alice thinks of a real number between 0 and 1, and Bob has to guess it. Bob begins by guessing 0.5, and so on. Clearly, in this case, no matter how many questions Bob asks, there will still be an infinite number of possibilities, though he can get greater and greater accuracy by asking more and more questions. (For example, after 10 questions, he might have narrowed down the range to (0.1015625, 0.1025390625)). However, in computer science, we are often satisfied if we can approximate the correct answer to arbitrary precision, rather than determine it exactly outright. (After all, the native real types of most microprocessors (see [[IEEE 754]]) can only store a fixed number of bits of precision, anyway.) Here, if, for example, Bob wants to determine Alice's number to an accuracy of one part in 10<sup>9</sup>, then he has to ask about 30 questions, because the length of the original interval is 1, and this must be reduced by a factor of 10<sup>9</sup>, which is about 2<sup>30</sup>. In general, the time taken will be approximately <math>\log_2\frac{\ell}{\epsilon_a}</math>, where <math>\ell</math> is the length of the original interval and <math>\epsilon_a</math> is the desired precision (expressed as absolute error).
 ==Problems==
@@ Line 118: / Line 128: @@
 * {{Problem|ccc08s2p6|Landing}}
 * {{Problem|ccc96s5|Max Distance}}
 * {{Problem|ccc03s5|Trucking Troubles}}
 * {{SPOJ|AGGRCOW|Aggressive Cows @ SPOJ}}

@@ Line 1: / Line 1: @@
 '''Binary search''' is the term used in computer science for the discrete version of the ''bisection method'', in which given a monotone function <math>f</math> over a discrete interval <math>I</math> and a target value <math>c</math> one wishes to find <math>x \in I</math> for which <math>f(x) \approx c</math>. It is most often used to locate a value in a sorted [[array]]. The term may also be used for the continuous version.
-==Discrete: array==
+==Informal introduction: the guessing game==
-In the most commonly encountered variation of binary search, we are given a zero-indexed [[array]] <math>A</math> of size <math>n</math> that is sorted in ascending order, along with some value <math>c</math>. Here the domain of the function <math>f</math> is the set of indices into the array, and <math>f(i) = A_i</math> where <math>A_i</math> is the element at the <math>i</math><sup>th</sup> position. There are two slightly different variations on what we wish to do:
+In the ''number guessing game'', there are two players, Alice and Bob. Alice announces that she has thought of an integer between 1 and 100 (inclusive), and challenges Bob to guess it. Bob may guess any number from 1 to 100, and Alice will tell him whether his guess is correct; if it is not correct, she will tell him (truthfully) either that her number is higher than his guess, or that it is lower.
 * ''Lower bound'': Here are two equivalent formulations:
 :# Find the ''first'' index into <math>A</math> where we could insert a new element of value <math>c</math> without violating the ascending order.
@@ Line 15: / Line 24: @@
 * The element immediately preceding the lower bound is the last element with value less than <math>c</math>, if this exists, or the hypothetical element at index -1, otherwise.
 * The element immediately preceding the upper bound is the last element with value less than or equal to <math>c</math>, if this exists, or the hypothetical element at index -1, otherwise.
 Both lower bound and upper bound can easily be found by iterating through the array from beginning to end, which takes <math>O(n)</math> comparisons and hence <math>O(n)</math> time if the elements of the array are simple scalar variables that take <math>O(1)</math> time to compare. However, because the array is sorted, we can do better than this. We begin with the knowledge that the element we seek might be anywhere in the array, or it could be "just past the end". Now, examine an element near the centre of the array. If this is less than the element we seek, we know the element we seek must be in the second half of the array. If it is greater, we know the element we seek must be in the first half. Thus, by making one comparison, we cut the range under consideration into half. It follows that after <math>O(\log n)</math> comparisons, we will be able to locate either the upper bound or the lower bound as we desire.
@@ Line 78: / Line 89: @@
 Additionally, if the array can be very large, then <code>m</code> should be computed as <code>l + (r-l)/2</code>, instead of <code>(l+r)/2</code>, in order to avoid possible arithmetic overflow.
-==Discrete: function==
+==Inverse function computation==
-More generally, we have some monotone function <math>f</math> which is easy to compute, and we need to compute its inverse, which, on the face, seems to be tricky. It is also not immediately obvious that we can make this abstraction from a given problem, but once the abstraction is discovered, a simple and efficient solution to the problem immediately follows.
+Both the number guessing game and the array search can be expressed as specific cases of the more general problem of ''discrete inverse function computation'', hinted at in the lead section of this article.
-The example problem we will consider is... TODO.
+We suppose:
 ==Continuous==
 TODO
 [[Category:Incomplete]]

@@ Line 67: / Line 67: @@
 ===Possible bugs===
-One obvious bug is absentmindedly setting <code>r = n-1</code> initially. Doing this will prevent the value <code>n</code> from ever being returned, which renders the implementation correct whenever the answer is less than <code>n</code>, but incorrect whenever it is <code>n</code>. (It will simply return <code>n-1</code> in this case.)
+As suggested below, the programmer has at least six opportunities to err.
-Another obvious bug is using <code>while (l &lt;= r)</code> instead of <code>while (l &lt; r)</code>. This will always cause an infinite loop in which the <code>else</code> branch is taken in every subsequent iteration.
+Additionally, if the array can be very large, then <code>m</code> should be computed as <code>l + (r-l)/2</code>, instead of <code>(l+r)/2</code>, in order to avoid possible arithmetic overflow.
-A third obvious bug is either comparing <code>A[m]</code> with <code>c</code> in the wrong direction, that is, writing <code>A[m] &gt; c</code>, <code>A[m] &gt;= c</code>, <code>c &lt; A[m]</code>, or <code>c &lt;= A[m]</code>, or reversing the order of the two branches. This would not correspond to the theory, and would almost always given an incorrect result.
+==Discrete: function==
-However, there are still four degrees of freedom in the implementation:
+The example problem we will consider is... TODO.
-# Should we compute <code>m</code> as the floor of the arithmetic mean of <code>l</code> and <code>r</code>, or as the ceiling?
-# Should we compare <code>A[m]</code> with <code>c</code> strictly, that is, with <code>&lt;</code>, or non-strictly, that is, with <code>&lt;=</code>?
+==Continuous==
-# Should we set <code>l = m+1</code>, <code>l = m</code>, or <code>l = m-1</code> in the first branch?
+TODO
-# Should we set <code>r = m+1</code>, <code>r = m</code>, or <code>r = m-1</code> in the second branch?
-These variations are covered in the page [[Binary search/Implementation details]].
+[[Category:Incomplete]]

@@ Line 71: / Line 71: @@
 # The index we are seeking is at most <code>r</code>.
 This is certainly true immediately before the first iteration of the loop, where <code>l = 0</code> and <code>r = n</code>. Now we claim that if it is true before a given iteration of the loop, it will be true after that iteration, which, by induction, implies our claim. First, the value <code>m</code> will be exactly the arithmetic mean of <code>l</code> and <code>r</code>, if their sum is even, or it will be 0.5 less than the mean, if their sum is odd, since <code>m</code> is computed as the arithmetic mean rounded down. This implies that, in any given iteration of the loop, <code>m</code>'s initial value will be at least <code>l</code>, and strictly less than <code>r</code>. Now:
-* ''Case 1'': <code>A[m] &lt; c</code>. This means that no element with index between <code>l</code> and <code>m</code>, inclusive, can be greater than <code>c</code>, because the array is sorted. But because we know that such an element exists (or that it is the hypothetical element just past the end of the array) in the current range delineated by indices <code>l</code> and <code>r</code>, we conclude that it must be in the second half of the range with indices from <code>m+1</code> to <code>r</code>, inclusive. In this case we set <code>l = m+1</code> and at the end of the loop the invariant is again satisfied. This is guaranteed to increase the value of <code>l</code>, since <code>m</code> starts out with value at least <code>l</code>. It also does not increase <code>l</code> beyond <code>r</code>, since <code>m</code> is initially strictly less than <code>m</code>.
+* ''Case 1'': <code>A[m] &lt; c</code>. This means that no element with index between <code>l</code> and <code>m</code>, inclusive, can be greater than <code>c</code>, because the array is sorted. But because we know that such an element exists (or that it is the hypothetical element just past the end of the array) in the current range delineated by indices <code>l</code> and <code>r</code>, we conclude that it must be in the second half of the range with indices from <code>m+1</code> to <code>r</code>, inclusive. In this case we set <code>l = m+1</code> and at the end of the loop the invariant is again satisfied. This is guaranteed to increase the value of <code>l</code>, since <code>m</code> starts out with value at least <code>l</code>. It also does not increase <code>l</code> beyond <code>r</code>, since <code>m</code> is initially strictly less than <code>r</code>.
 * ''Case 2'': <code>A[m] &gt;= c</code>. This means that there exists an element with index between <code>l</code> and <code>m</code>, inclusive, which is at least <code>c</code>. This implies that the first such element is somewhere in this half of the range, because the array is sorted. Therefore, after setting <code>r = m</code>, the range of indices between <code>l</code> and <code>r</code>, inclusive, will still contain the index we are seeking, and hence the invariant is again satisfied. This is guaranteed to decrease the value of <code>r</code>, since <code>m</code> starts out strictly less than <code>r</code>; it also will not decrease it beyond <code>l</code>, since <code>m</code> starts out at least as large as <code>l</code>.
 Since each iteration of the loop either increases <code>l</code> or decreases <code>r</code>, the loop will eventually terminate with <code>l = r</code>. Since the invariant still holds, this unique common value must be the solution. <math>_{\blacksquare}</math>

@@ Line 55: / Line 55: @@
+     {
          int m = (l+r)/2;
-         if (A[m] <= c)       /* Note use of < instead of <=. */
+         if (A[m] <= c)       /* Note use of <= instead of <. */
              l = m+1;
          else