Editing Binary search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
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. | '''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 | + | 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: | * ''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. | :# 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 24: | Line 15: | ||
* 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 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. | * 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. | 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 55: | Line 44: | ||
{ | { | ||
int m = (l+r)/2; | int m = (l+r)/2; | ||
− | if (A[m] <= c) /* Note use of < | + | if (A[m] <= c) /* Note use of < instead of <=. */ |
l = m+1; | l = m+1; | ||
else | else | ||
Line 71: | Line 60: | ||
# The index we are seeking is at most <code>r</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: | 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> | + | * ''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>. | * ''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> | 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 89: | Line 78: | ||
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. | 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== |
− | + | 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. | |
− | + | The example problem we will consider is... TODO. | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
==Continuous== | ==Continuous== | ||
− | + | TODO | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | [[Category:Incomplete]] | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + |