9 ms·

Binary search with confidence

94 points by tylerhou 5y ago

rochak 5y ago
Thanks! This helped me get a basic understanding of how to frame a binary search solution not just for stuff that has to fit in a natural order.
OscarCunningham 5y ago
Because I'm used to half-open intervals, I would have used the invariant left <= target < right Or in other words target in range(left,right). The article would phrase this as making the target green rather than red. The code would end up very similar, except at the start you can initialize right to len(array) rather than len(array)-1, which is a bit cleaner. Also I would write the while loop condition as while right - left > 1: i.e. 'while we have more than one option remaining'.
- cleancoder0 5y ago
  I believe half-open intervals is something C++ uses for std::lower_bound and std::upper_bound.
  - thaumasiotes 5y ago
    Half-open intervals are very common because they overlap perfectly.
  - mark-r 5y ago
    Using half-open intervals for std::lower_bound and std::upper_bound has an unexpected benefit. It allows the functions to return an insertion point that keeps the sequence sorted, even if that insertion point is at the end of the sequence.
- hddqsb 5y ago
  This invariant has some surprising effects: - When the target appears multiple times, the search will find the last occurrence rather than the first. - If you return `right`, then you get the behaviour of C++'s std::upper_bound and Python's bisect.bisect_right: The return value is the index of the first element strictly greater than the target, or `len(array)` if all the elements are less than or equal to the target. - If you return `left`, you get a somewhat unusual beast: The return value is the index of the last element less than or equal to the target. If all the elements are greater than the target, the return value should be -1 (because returning 0 would incorrectly suggest that `array[0] <= target`). Initialising `right` to `len(array)` removes one of the special cases (which is nice and can be done regardless of the invariant), but if `left` remains initialised to 0 then a special case would still be necessary to distinguish between "the first element is equal to the target" and "all the elements are greater than the target" (this special case can be eliminated by initialising `left` to -1; see my top-level comment). Inclusive-exclusive intervals are a great in many cases, but a little pragmatism can make life easier. P.S. I also write `while right - left > 1`.
  - deleted 5y ago
    [deleted]
caladin 5y ago
Binary search is deceptively simple. It is quite fertile ground for off-by-one errors, integer overflow, infinite loops, etc. Wikipedia has an entire section dedicated to this here: https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem... When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases. A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.
- rustybolt 5y ago
  I agree that binary search is prone to errors, but the overflow error is just calculating the midpoint as (low + high) / 2 I mean, that's technically true because it might crash for huge arrays, but if this is a bug then the follow implementation of a function that adds to integers is also buggy, since it will overflow when x + y doesn't fit in an int: int add(int x, int y) { return x + y; }
  - tylerhou 5y ago
    Also, no integer overflow in Python, so no bug here.
    - rustybolt 5y ago
      Very true! Which is also why I used a C-like syntax in the snippet ;)
  - anonymoushn 5y ago
    I don't think this is an unfair gotcha. If you have u32 for low and high, and someone gives you an array with 4 billion entries, you can return the correct value if you compute the midpoint correctly.
jonsen 5y ago
If interested in a comprehensive treatment of this kind of imperative program design: The Science of Programming by David Gries.
charcircuit 5y ago
>Then, admire how the loop body writes itself. There is no equality check, no +1/-1 arithmetic: just move the correct-color pointer. The +1/-1 is an optimization because you know what you are searching for isn't at that index. You no longer need to keep that mid point in your new search space.
- tylerhou 5y ago
  I think you're right that I don't do the "normal" implementation quite enough justice; I've been meaning to write a third followup binary search post to "redeem" it. As others have mentioned, you can prove it correct with a simple invariant: the value that you are looking for is in the narrowed range (if it is in the array to begin with). But I think that invariant is harder to write code for, which is the point of this article (maybe I should state that explicitly). That said, you can only use the +1/-1 optimization when you are searching for a particular element, so you can no longer use a function that returns true/false; you need a third state to distinguish equality. So it's also not as theoretically "pure" as I would like. But not only is it less pure, it's also not applicable to other real problems (see the followup post: https://blog.tylerhou.io/posts/binary-search-revisited/ https://blog.tylerhou.io/posts/binary-search-revisited/). That's also why I don't really like it as it makes binary search too restrictive. I think it's a major failure that we teach people that binary search is an algorithm for finding a value in a sorted array—it's really a much more powerful and general algorithm for finding a transition point in a monotonic function from {ints, reals, any totally-ordered set} to booleans. That's another reason I prefer this approach, not just simplicity in implementation.
  - anonymoushn 5y ago
    > That said, you can only use the +1/-1 optimization when you are searching for a particular element, so you can no longer use a function that returns true/false; you need a third state to distinguish equality. So it's also not as theoretically "pure" as I would like. But not only is it less pure, it's also not applicable to other real problems (see the followup post: https://blog.tylerhou.io/posts/binary-search-revisited/ https://blog.tylerhou.io/posts/binary-search-revisited/). Why do you need a third state? The spec for your binary search says that it returns the first non-green element. A common spec for binary searches on arrays is that it should return the first element that is not < needle, and your blog includes an example of using your generalized binary search this way. I think a working binary search for arbitrary functions on integers that uses this "optimization" follows: # search [lo, hi) for the least integer x with !is_green(x) # or hi if they are all green # or lo if you pass in a malformed interval def binary_search(lo, hi, is_green): while hi > lo: mid = lo + (hi - lo) // 2 if is_green(mid): # we will definitely return a value greater than # mid, since mid is green. # let's only look at elements past the known-green ones. lo = mid+1 else: # hi is the greatest value we can return, # even though we'll never look at it, # so mid is a good value for hi here # (in particular, if hi==lo+1, then mid==lo, and # the above branch can set lo=hi before we exit # the loop and return lo) hi = mid return lo # Usage. binary_search(0, len(array), lambda i: array[i] < 6) It seems like the difficulty you encountered with this approach is to do with the fact that you'd like to use an invariant in which you have at least one red and at least one green element. If you relax that self-imposed requirement then you can apparently delete half of the code. Edit: I had a hard time articulating the invariant for the above binary search, which I commonly write for arrays only. I think it's "Given an interval [lo, hi) in which elements monotonically 0-or-more green then 0-or-more red, and given that (-inf, lo) is all green and that [hi, inf) is all red, let's find the least red element." This is a surprising amount of complexity, but I guess I'd rather have the complexity in the English description of the invariant than in the code. If someone has a more concise rationale for shoving both red and green mids out of the interval under consideration, that would be swell. In your followup article, you have: if left >= right: return 0 if not is_green(left): return 0 if is_green(right): return right + 1 This is a bit weird. It seems like if I give you an all-green interval of length 0, 1, or 2, I should get 1-past-the-end in all of those cases, but here we get 0, 0, and 1-past-the-end. It's weird to get 0 if our interval is all-green [999,999] then get 1001 if we ask about all-green [999,1000]. It also seems like if I give you an all-red interval like [-1000,1000], you shouldn't return 0, since that element has a lot of red elements before it.
thenoblesunfish 5y ago
Very nice! I always struggled with binary search programming problems until I starting frame things in a similar way: Check a certain condition, return the appropriate answer when it's false, write a guaranteed-to-terminate loop that maintains that same condition as an invariant, then interpret the final state to return the appropriate answer.
maple3142 5y ago
Sometimes, I find it is easier to make your base case broader and bruteforce it one by one when you couldn't get it right. For example, when I tried to exploit RSA parity oracle I couldn't find the right answer when it is narrowed to the smallest range for some unknown reason. Changing the loop condition to `while right-left>1000` works pretty well if you don't want to debug it more.
danuker 5y ago
The best way I've seen to handle such problems full of possible mistakes is to use Test-Driven Development. Write a test for a trivial case, like a zero-length array. Think of the design. What should it return? Should it throw an exception? Do that, and only that, in the implementation. Each iteration after you add a test, you should first focus on getting every test to pass, then commit to version control, then refactor to get the clearest implementation. A next iteration would be to test with a single element - a matching one, case in which it should return its index (zero in zero-indexed languages). Then with a non-matching one - again, you have to make a design decision: throw an exception, return -1, or something else. Then a case with two elements, when the first is the match. Then two with the second matching. Then two with none matching. For as long as you can think of tests breaking your implementation, keep thinking of edge-cases. Eventually you end up with a formidable collection of test cases, and you will not be afraid of refactoring or changing things, because you will find out quickly and easily which tests break. Edit: boxed mentioned Property-Based Testing and Mutation Testing. These are amazing ways to come up with more corner cases to cover.
- boxed 5y ago
  Property Based Testing and Mutation Testing is much better than trying to come up with examples by thinking hard.
  - danuker 5y ago
    I stand corrected. These methods are indeed even better when you can't think of more examples.
  - qcoh 5y ago
    PBT is awesome but I would still like to have tests I can easily reason about when implementing a tricky algorithm. The way I see it, TDD is the specification, PBT is for finding gaps in my specification.
    - boxed 5y ago
      Mutation testing is for finding holes in the tests. PBT is for finding holes in your code.
beeforpork 5y ago
Yes, exactly, binary search is full of traps. And you may have missed one: (left + right) // 2 is better written 'left + ((right - left) // 2)'. At least on some languages, I don't know which type Python will use there. 'Nearly All Binary Searches and Mergesorts are Broken': https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1 https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- marginalia_nu 5y ago
  It could potentially be a pretty good interview question to weed out those who have spent the last 6 months memorizing algorithms. Realistically, anyone with programming experience would immediately question the premise of being asked to implement a binary search on a whiteboard because realistically the only way anyone will succeed is by having memorized an implementation.
  - anonymoushn 5y ago
    I don't think this is an especially great question, but I worked at one company that asked this question and most people who got it right did not seem to have an implementation memorized. I say this because they got it right only after writing a buggy version and fixing some bugs. Another company was in the habit of asking a different question that gets to the heart of the matter of "Can you think with invariants?" but is not nearly as tricky as binary search. That seemed better to me.
  - mannykannot 5y ago
    It is a very useful question if you do not simply check whether the result is correct, but instead use it as a way to evaluate the candidate's problem-solving skills.
- 10000truths 5y ago
  This can still cause signed overflow if left is close enough to INT_MAX and right is close enough to INT_MIN. The actual overflow-less way to compute the average of two numbers is: (a/2) + (b/2) + (((a%2) + (b%2))/2)
deleted 5y ago
[deleted]
orlp 5y ago
I am a huge proponent of "bitwise" binary search. Consider r to be the result index we wish to find in range [0, n), that is, the first index where a predicate returns false, or n if there is no such predicate. We can construct this index bit-by-bit, starting from the most significant bit: # Extracts the highest set bit for n > 0. # This can be 1-5 instructions on most machines using count leading zeros. def highest_bit_set(n): return 1 << (n.bit_length() - 1) def binary_search(n, predicate): # Construct largest possible r such that predicate(r) is true, or 0. if n == 0: return 0 r = 0 bit = highest_bit_set(n) while bit: if (r | bit) < n and predicate(r | bit): r |= bit bit >>= 1 # Return smallest possible r such that predicate(r) is false, or n. if r > 0 or predicate(0): r += 1 return r I find this to be significantly easier to reason about, although I do have a lot of experience with bitwise manipulation. And it is trivial to extend to search a range [lo, hi): def binary_search_range(lo, hi, predicate): return binary_search(hi - lo, lambda i: predicate(lo + i)) It's similarly trivial to reason they do exactly log2(n) or log2(hi - lo) iterations and are thus worst-case optimal.
- hddqsb 5y ago
  Note that with this version, the expected number of calls to `predicate` can be 1 more than strictly necessary (depending on n). This happens when n is one more than a power of 2, e.g. if n is 65 then `bit` is 64 and the first call will be `predicate(64)`, which is basically useless in reducing the search space.
  - orlp 5y ago
    This is true, if your comparison operator is very expensive you should (very, very carefully) implement the traditional binary search.
- truly 5y ago
  This is called bisection search (search for the largest/smallest value satisfying a given predicate). It also reminds me a little bit of exponential search (upper bound unknown), although obviously the upper bound is known in your implementation. Bisection: https://en.wikipedia.org/wiki/Bisection_method https://en.wikipedia.org/wiki/Bisection_method Exponential search: https://en.wikipedia.org/wiki/Exponential_search https://en.wikipedia.org/wiki/Exponential_search A practical application of bisection search is in git bisect (https://git-scm.com/docs/git-bisect https://git-scm.com/docs/git-bisect) to find the first revision that introduced a bug.
atfzl 5y ago
The code with this method looks a lot ugly for the basic binary search where you return -1 when an element isn't found. https://leetcode.com/problems/binary-search/ https://leetcode.com/problems/binary-search/ JavaScript code: function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; // empty arr, so we won't find anything if (!arr.length) { return -1; } // the target is less than the smallest number in arr if (target < arr[left]) { return -1; } // the target is greater then the smallest number in arr if (arr[right] < target) { return -1; } // These two `if` are needed for the case when there are only 2 elements // in the array. if (arr[left] === target) { return left; } if (arr[right] === target) { return right; } while (left + 1 !== right) { const middle = left + Math.floor((right - left) / 2); if (arr[middle] < target) { left = middle; } else { right = middle; } } if (arr[right] === target) { return right; } return -1; }
truly 5y ago
A while ago, I have made a video tutorial on binary search which explains it visually: https://www.youtube.com/watch?v=uHpRuBdcYtI https://www.youtube.com/watch?v=uHpRuBdcYtI. The visual explanation in this article is also very nice (color the items less than the value to search for with green, items larger with red), and it shows how people can have different intuitions over how and why an algorithm works.
jqpabc123 5y ago
Why bring color into it? Left/right or lower/upper work just as well and correlate better to the actual math involved.
- chmaynard 5y ago
  A related question: When I use the Print command in Safari (macOS) to convert the blog post into a PDF document, the background colors are not rendered. Does anyone know why?
  - jqpabc123 5y ago
    This is typically a browser setting. Most browsers are set to NOT print background colors/images by default. With Google Chrome for example, you have to enable "Background images" in the print settings panel (Ctrl+P).
- tylerhou 5y ago
  A previous version of the post used true/false, but I think color is easier to understand after revision (e.g. "left always points to an element corresponding to true" -> "left always points to a green element").
hddqsb 5y ago
I love the colouring approach, that's same approach I use when explaining/analysing binary search. One advantage of this approach that was not explicitly mentioned is that the behaviour is clear and well-defined when the target element appears multiple times, unlike some implementations where it is unspecified which occurrence will be found. Minor point: I prefer to negate the predicate, i.e. "is_red" instead of "is_green". Then the definition of the binary_search is "return the first index for which the predicate returns true", which I find more natural. But the three if-statements for the base cases are horrible and completely unnecessary! We can't initialise `left` to 0 because that might violate the invariant (it is possible that `is_green(arr[0])` will return False). However, we can initialise `left` to -1 (!) if we define `is_green(arr[-1])` to be True, and make sure to never actually compute `is_green(arr[-1])`. (Note when I say `arr[-1]` I am referring to the fictional element before the first element, not the element specified by Python's negative index rules.) Similarly, we can initialise `right` to `len(arr)` if we define `is_green(arr[len(arr)])` to be False. So the first line becomes left, right = -1, len(array) and the three if-statements can be deleted. This uses an exclusive-exclusive range, which can be a little unsettling for people used to inclusive-exclusive ranges. But I think the elegance of the invariants totally justifies it. Another reason I prefer exclusive-exclusive over inclusive-exclusive for this is that it makes the rounding in `(left + right) // 2` consistent with the "uniqueness" of the middle. An array with 3 items has a unique middle (index 1), while an array with 4 items has two "middles" (index 1 and index 2). With an inclusive-exclusive range, the rounding does not reflect this: when the size is 3, `(0 + 3) / 2` gives 1.5 (which must be truncated to give the correct index); when the size is 4, `(0 + 4) / 2` gives 2.0 (which arbitrarily picks index 2). It bothers me that the case with a unique middle involves rounding (which must be done in the correct direction!) and the case with no unique middle returns a misleadingly exact result. With an exclusive-exclusive range on the other hand, it all works nicely: when the size is 3, `(-1 + 3) / 2` gives 1.0 (which is the unique middle); and when the size is 4, `(-1 + 4) / 2` gives 1.5 (which can be rounded up or down to get the two "middles").
nemetroid 5y ago
I think the reframing of the problem does make it look easier at first, but then you end up needing those three special cases which in my opinion negates the elegance. Also, since the reframed problem never terminates early, the described algorithm always has the same number of lookups (i.e. you always get the worst-case).
- hddqsb 5y ago
  The three special cases are unnecessary (see my top-level comment). Implementations that terminate early might seem faster at fist glance, but they can actually be slower: they only save 1 iteration on average*, and they require up to 2 branches in each iteration instead of 1. The cost of doubling the number of branches can outweigh the savings (1 iteration out of log2(n)). A possible exception is if the comparison function is expensive and returns a rich comparison (less/equal/greater), in which case it might make sense to perform the 2 branches. But a much more significant disadvantage of terminating early is that when the target element appears multiple times, there is no guarantee which occurrence will be found. *Incomplete proof that the saving is only 1 iteration on average: n/2 cases will not terminate early, n/4 will terminate 1 iteration early, n/8 will terminate 2 iterations early, n/16 will terminate 3 iterations early, etc. So the total saving is n/4*1 + n/8*2 + n/16*3 + ... which is at most n (the proof is the same as for the time complexity of the "heapify" operation).

94 points by tylerhou 5y ago

Thanks! This helped me get a basic understanding of how to frame a binary search solution not just for stuff that has to fit in a natural order.

OscarCunningham 5y ago

Because I'm used to half-open intervals, I would have used the invariant left <= target < right Or in other words target in range(left,right). The article would phrase this as making the target green rather than red. The code would end up very similar, except at the start you can initialize right to len(array) rather than len(array)-1, which is a bit cleaner. Also I would write the while loop condition as while right - left > 1: i.e. 'while we have more than one option remaining'.

cleancoder0 5y ago
I believe half-open intervals is something C++ uses for std::lower_bound and std::upper_bound.
- thaumasiotes 5y ago
  Half-open intervals are very common because they overlap perfectly.
- mark-r 5y ago
  Using half-open intervals for std::lower_bound and std::upper_bound has an unexpected benefit. It allows the functions to return an insertion point that keeps the sequence sorted, even if that insertion point is at the end of the sequence.
hddqsb 5y ago
This invariant has some surprising effects: - When the target appears multiple times, the search will find the last occurrence rather than the first. - If you return `right`, then you get the behaviour of C++'s std::upper_bound and Python's bisect.bisect_right: The return value is the index of the first element strictly greater than the target, or `len(array)` if all the elements are less than or equal to the target. - If you return `left`, you get a somewhat unusual beast: The return value is the index of the last element less than or equal to the target. If all the elements are greater than the target, the return value should be -1 (because returning 0 would incorrectly suggest that `array[0] <= target`). Initialising `right` to `len(array)` removes one of the special cases (which is nice and can be done regardless of the invariant), but if `left` remains initialised to 0 then a special case would still be necessary to distinguish between "the first element is equal to the target" and "all the elements are greater than the target" (this special case can be eliminated by initialising `left` to -1; see my top-level comment). Inclusive-exclusive intervals are a great in many cases, but a little pragmatism can make life easier. P.S. I also write `while right - left > 1`.
- deleted 5y ago
  [deleted]

caladin 5y ago

Binary search is deceptively simple. It is quite fertile ground for off-by-one errors, integer overflow, infinite loops, etc. Wikipedia has an entire section dedicated to this here: https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem... When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases. A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.

rustybolt 5y ago
I agree that binary search is prone to errors, but the overflow error is just calculating the midpoint as (low + high) / 2 I mean, that's technically true because it might crash for huge arrays, but if this is a bug then the follow implementation of a function that adds to integers is also buggy, since it will overflow when x + y doesn't fit in an int: int add(int x, int y) { return x + y; }
- tylerhou 5y ago
  Also, no integer overflow in Python, so no bug here.
  - rustybolt 5y ago
    Very true! Which is also why I used a C-like syntax in the snippet ;)
- anonymoushn 5y ago
  I don't think this is an unfair gotcha. If you have u32 for low and high, and someone gives you an array with 4 billion entries, you can return the correct value if you compute the midpoint correctly.

jonsen 5y ago

If interested in a comprehensive treatment of this kind of imperative program design: The Science of Programming by David Gries.

charcircuit 5y ago

>Then, admire how the loop body writes itself. There is no equality check, no +1/-1 arithmetic: just move the correct-color pointer. The +1/-1 is an optimization because you know what you are searching for isn't at that index. You no longer need to keep that mid point in your new search space.

tylerhou 5y ago
I think you're right that I don't do the "normal" implementation quite enough justice; I've been meaning to write a third followup binary search post to "redeem" it. As others have mentioned, you can prove it correct with a simple invariant: the value that you are looking for is in the narrowed range (if it is in the array to begin with). But I think that invariant is harder to write code for, which is the point of this article (maybe I should state that explicitly). That said, you can only use the +1/-1 optimization when you are searching for a particular element, so you can no longer use a function that returns true/false; you need a third state to distinguish equality. So it's also not as theoretically "pure" as I would like. But not only is it less pure, it's also not applicable to other real problems (see the followup post: https://blog.tylerhou.io/posts/binary-search-revisited/ https://blog.tylerhou.io/posts/binary-search-revisited/). That's also why I don't really like it as it makes binary search too restrictive. I think it's a major failure that we teach people that binary search is an algorithm for finding a value in a sorted array—it's really a much more powerful and general algorithm for finding a transition point in a monotonic function from {ints, reals, any totally-ordered set} to booleans. That's another reason I prefer this approach, not just simplicity in implementation.
- anonymoushn 5y ago
  > That said, you can only use the +1/-1 optimization when you are searching for a particular element, so you can no longer use a function that returns true/false; you need a third state to distinguish equality. So it's also not as theoretically "pure" as I would like. But not only is it less pure, it's also not applicable to other real problems (see the followup post: https://blog.tylerhou.io/posts/binary-search-revisited/ https://blog.tylerhou.io/posts/binary-search-revisited/). Why do you need a third state? The spec for your binary search says that it returns the first non-green element. A common spec for binary searches on arrays is that it should return the first element that is not < needle, and your blog includes an example of using your generalized binary search this way. I think a working binary search for arbitrary functions on integers that uses this "optimization" follows: # search [lo, hi) for the least integer x with !is_green(x) # or hi if they are all green # or lo if you pass in a malformed interval def binary_search(lo, hi, is_green): while hi > lo: mid = lo + (hi - lo) // 2 if is_green(mid): # we will definitely return a value greater than # mid, since mid is green. # let's only look at elements past the known-green ones. lo = mid+1 else: # hi is the greatest value we can return, # even though we'll never look at it, # so mid is a good value for hi here # (in particular, if hi==lo+1, then mid==lo, and # the above branch can set lo=hi before we exit # the loop and return lo) hi = mid return lo # Usage. binary_search(0, len(array), lambda i: array[i] < 6) It seems like the difficulty you encountered with this approach is to do with the fact that you'd like to use an invariant in which you have at least one red and at least one green element. If you relax that self-imposed requirement then you can apparently delete half of the code. Edit: I had a hard time articulating the invariant for the above binary search, which I commonly write for arrays only. I think it's "Given an interval [lo, hi) in which elements monotonically 0-or-more green then 0-or-more red, and given that (-inf, lo) is all green and that [hi, inf) is all red, let's find the least red element." This is a surprising amount of complexity, but I guess I'd rather have the complexity in the English description of the invariant than in the code. If someone has a more concise rationale for shoving both red and green mids out of the interval under consideration, that would be swell. In your followup article, you have: if left >= right: return 0 if not is_green(left): return 0 if is_green(right): return right + 1 This is a bit weird. It seems like if I give you an all-green interval of length 0, 1, or 2, I should get 1-past-the-end in all of those cases, but here we get 0, 0, and 1-past-the-end. It's weird to get 0 if our interval is all-green [999,999] then get 1001 if we ask about all-green [999,1000]. It also seems like if I give you an all-red interval like [-1000,1000], you shouldn't return 0, since that element has a lot of red elements before it.

thenoblesunfish 5y ago

Very nice! I always struggled with binary search programming problems until I starting frame things in a similar way: Check a certain condition, return the appropriate answer when it's false, write a guaranteed-to-terminate loop that maintains that same condition as an invariant, then interpret the final state to return the appropriate answer.

maple3142 5y ago

Sometimes, I find it is easier to make your base case broader and bruteforce it one by one when you couldn't get it right. For example, when I tried to exploit RSA parity oracle I couldn't find the right answer when it is narrowed to the smallest range for some unknown reason. Changing the loop condition to `while right-left>1000` works pretty well if you don't want to debug it more.

danuker 5y ago

The best way I've seen to handle such problems full of possible mistakes is to use Test-Driven Development. Write a test for a trivial case, like a zero-length array. Think of the design. What should it return? Should it throw an exception? Do that, and only that, in the implementation. Each iteration after you add a test, you should first focus on getting every test to pass, then commit to version control, then refactor to get the clearest implementation. A next iteration would be to test with a single element - a matching one, case in which it should return its index (zero in zero-indexed languages). Then with a non-matching one - again, you have to make a design decision: throw an exception, return -1, or something else. Then a case with two elements, when the first is the match. Then two with the second matching. Then two with none matching. For as long as you can think of tests breaking your implementation, keep thinking of edge-cases. Eventually you end up with a formidable collection of test cases, and you will not be afraid of refactoring or changing things, because you will find out quickly and easily which tests break. Edit: boxed mentioned Property-Based Testing and Mutation Testing. These are amazing ways to come up with more corner cases to cover.

boxed 5y ago
Property Based Testing and Mutation Testing is much better than trying to come up with examples by thinking hard.
- danuker 5y ago
  I stand corrected. These methods are indeed even better when you can't think of more examples.
- qcoh 5y ago
  PBT is awesome but I would still like to have tests I can easily reason about when implementing a tricky algorithm. The way I see it, TDD is the specification, PBT is for finding gaps in my specification.
  - boxed 5y ago
    Mutation testing is for finding holes in the tests. PBT is for finding holes in your code.

beeforpork 5y ago

Yes, exactly, binary search is full of traps. And you may have missed one: (left + right) // 2 is better written 'left + ((right - left) // 2)'. At least on some languages, I don't know which type Python will use there. 'Nearly All Binary Searches and Mergesorts are Broken': https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1 https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

marginalia_nu 5y ago
It could potentially be a pretty good interview question to weed out those who have spent the last 6 months memorizing algorithms. Realistically, anyone with programming experience would immediately question the premise of being asked to implement a binary search on a whiteboard because realistically the only way anyone will succeed is by having memorized an implementation.
- anonymoushn 5y ago
  I don't think this is an especially great question, but I worked at one company that asked this question and most people who got it right did not seem to have an implementation memorized. I say this because they got it right only after writing a buggy version and fixing some bugs. Another company was in the habit of asking a different question that gets to the heart of the matter of "Can you think with invariants?" but is not nearly as tricky as binary search. That seemed better to me.
- mannykannot 5y ago
  It is a very useful question if you do not simply check whether the result is correct, but instead use it as a way to evaluate the candidate's problem-solving skills.
10000truths 5y ago
This can still cause signed overflow if left is close enough to INT_MAX and right is close enough to INT_MIN. The actual overflow-less way to compute the average of two numbers is: (a/2) + (b/2) + (((a%2) + (b%2))/2)

deleted 5y ago

[deleted]

orlp 5y ago

I am a huge proponent of "bitwise" binary search. Consider r to be the result index we wish to find in range [0, n), that is, the first index where a predicate returns false, or n if there is no such predicate. We can construct this index bit-by-bit, starting from the most significant bit: # Extracts the highest set bit for n > 0. # This can be 1-5 instructions on most machines using count leading zeros. def highest_bit_set(n): return 1 << (n.bit_length() - 1) def binary_search(n, predicate): # Construct largest possible r such that predicate(r) is true, or 0. if n == 0: return 0 r = 0 bit = highest_bit_set(n) while bit: if (r | bit) < n and predicate(r | bit): r |= bit bit >>= 1 # Return smallest possible r such that predicate(r) is false, or n. if r > 0 or predicate(0): r += 1 return r I find this to be significantly easier to reason about, although I do have a lot of experience with bitwise manipulation. And it is trivial to extend to search a range [lo, hi): def binary_search_range(lo, hi, predicate): return binary_search(hi - lo, lambda i: predicate(lo + i)) It's similarly trivial to reason they do exactly log2(n) or log2(hi - lo) iterations and are thus worst-case optimal.

hddqsb 5y ago
Note that with this version, the expected number of calls to `predicate` can be 1 more than strictly necessary (depending on n). This happens when n is one more than a power of 2, e.g. if n is 65 then `bit` is 64 and the first call will be `predicate(64)`, which is basically useless in reducing the search space.
- orlp 5y ago
  This is true, if your comparison operator is very expensive you should (very, very carefully) implement the traditional binary search.
truly 5y ago
This is called bisection search (search for the largest/smallest value satisfying a given predicate). It also reminds me a little bit of exponential search (upper bound unknown), although obviously the upper bound is known in your implementation. Bisection: https://en.wikipedia.org/wiki/Bisection_method https://en.wikipedia.org/wiki/Bisection_method Exponential search: https://en.wikipedia.org/wiki/Exponential_search https://en.wikipedia.org/wiki/Exponential_search A practical application of bisection search is in git bisect (https://git-scm.com/docs/git-bisect https://git-scm.com/docs/git-bisect) to find the first revision that introduced a bug.

atfzl 5y ago

The code with this method looks a lot ugly for the basic binary search where you return -1 when an element isn't found. https://leetcode.com/problems/binary-search/ https://leetcode.com/problems/binary-search/ JavaScript code: function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; // empty arr, so we won't find anything if (!arr.length) { return -1; } // the target is less than the smallest number in arr if (target < arr[left]) { return -1; } // the target is greater then the smallest number in arr if (arr[right] < target) { return -1; } // These two `if` are needed for the case when there are only 2 elements // in the array. if (arr[left] === target) { return left; } if (arr[right] === target) { return right; } while (left + 1 !== right) { const middle = left + Math.floor((right - left) / 2); if (arr[middle] < target) { left = middle; } else { right = middle; } } if (arr[right] === target) { return right; } return -1; }

truly 5y ago

A while ago, I have made a video tutorial on binary search which explains it visually: https://www.youtube.com/watch?v=uHpRuBdcYtI https://www.youtube.com/watch?v=uHpRuBdcYtI. The visual explanation in this article is also very nice (color the items less than the value to search for with green, items larger with red), and it shows how people can have different intuitions over how and why an algorithm works.

jqpabc123 5y ago

Why bring color into it? Left/right or lower/upper work just as well and correlate better to the actual math involved.

chmaynard 5y ago
A related question: When I use the Print command in Safari (macOS) to convert the blog post into a PDF document, the background colors are not rendered. Does anyone know why?
- jqpabc123 5y ago
  This is typically a browser setting. Most browsers are set to NOT print background colors/images by default. With Google Chrome for example, you have to enable "Background images" in the print settings panel (Ctrl+P).
tylerhou 5y ago
A previous version of the post used true/false, but I think color is easier to understand after revision (e.g. "left always points to an element corresponding to true" -> "left always points to a green element").

hddqsb 5y ago

I love the colouring approach, that's same approach I use when explaining/analysing binary search. One advantage of this approach that was not explicitly mentioned is that the behaviour is clear and well-defined when the target element appears multiple times, unlike some implementations where it is unspecified which occurrence will be found. Minor point: I prefer to negate the predicate, i.e. "is_red" instead of "is_green". Then the definition of the binary_search is "return the first index for which the predicate returns true", which I find more natural. But the three if-statements for the base cases are horrible and completely unnecessary! We can't initialise `left` to 0 because that might violate the invariant (it is possible that `is_green(arr[0])` will return False). However, we can initialise `left` to -1 (!) if we define `is_green(arr[-1])` to be True, and make sure to never actually compute `is_green(arr[-1])`. (Note when I say `arr[-1]` I am referring to the fictional element before the first element, not the element specified by Python's negative index rules.) Similarly, we can initialise `right` to `len(arr)` if we define `is_green(arr[len(arr)])` to be False. So the first line becomes left, right = -1, len(array) and the three if-statements can be deleted. This uses an exclusive-exclusive range, which can be a little unsettling for people used to inclusive-exclusive ranges. But I think the elegance of the invariants totally justifies it. Another reason I prefer exclusive-exclusive over inclusive-exclusive for this is that it makes the rounding in `(left + right) // 2` consistent with the "uniqueness" of the middle. An array with 3 items has a unique middle (index 1), while an array with 4 items has two "middles" (index 1 and index 2). With an inclusive-exclusive range, the rounding does not reflect this: when the size is 3, `(0 + 3) / 2` gives 1.5 (which must be truncated to give the correct index); when the size is 4, `(0 + 4) / 2` gives 2.0 (which arbitrarily picks index 2). It bothers me that the case with a unique middle involves rounding (which must be done in the correct direction!) and the case with no unique middle returns a misleadingly exact result. With an exclusive-exclusive range on the other hand, it all works nicely: when the size is 3, `(-1 + 3) / 2` gives 1.0 (which is the unique middle); and when the size is 4, `(-1 + 4) / 2` gives 1.5 (which can be rounded up or down to get the two "middles").

nemetroid 5y ago

I think the reframing of the problem does make it look easier at first, but then you end up needing those three special cases which in my opinion negates the elegance. Also, since the reframed problem never terminates early, the described algorithm always has the same number of lookups (i.e. you always get the worst-case).

hddqsb 5y ago
The three special cases are unnecessary (see my top-level comment). Implementations that terminate early might seem faster at fist glance, but they can actually be slower: they only save 1 iteration on average*, and they require up to 2 branches in each iteration instead of 1. The cost of doubling the number of branches can outweigh the savings (1 iteration out of log2(n)). A possible exception is if the comparison function is expensive and returns a rich comparison (less/equal/greater), in which case it might make sense to perform the 2 branches. But a much more significant disadvantage of terminating early is that when the target element appears multiple times, there is no guarantee which occurrence will be found. *Incomplete proof that the saving is only 1 iteration on average: n/2 cases will not terminate early, n/4 will terminate 1 iteration early, n/8 will terminate 2 iterations early, n/16 will terminate 3 iterations early, etc. So the total saving is n/4*1 + n/8*2 + n/16*3 + ... which is at most n (the proof is the same as for the time complexity of the "heapify" operation).