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.
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/).
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.
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)
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
def binary_search(left, right, is_green):
left -= 1
while left + 1 < right:
middle = (left + right) // 2
if is_green(middle):
left = middle
else:
right = middle
return right
# Usage.
binary_search(0, len(array), lambda i: array[i] < 6)
*Equivalent except for the rounding in the division.
For signed search ranges, if you modify my implementation above to compute the midpoint as (lo + hi) // 2 and (lo + hi) < 0 and the language rounds integer division toward zero, you gain a rounding-related bug. In this sort of circumstance, your approach does not gain that bug because it doesn't care which way division is rounded. Python doesn't have overflow and rounds down, so ~all of the errors we can make on that line won't happen anyway :)
If the range is unsigned, lo-1 is likely to be MAX_VALUE, but it seems like it still does the right thing.
1. The entire range isn't red, so at some point [proof needed] we will move left to a green element. From that point on we can continue analysis like normal. (I can't think of an easy way to prove such a claim without messing with floor division and induction, etc... but it seems intuitively true.)
2. The entire range is red, so green will never be moved, so right will point to the first element and green will point to one before the first. This returns the correct value.
I'll have to come up with a way to easily prove statement 1 above to be convinced that it is better. But I can include this version in the follow up.
(A less sneaky version is to explicitly define new predicates: `is_green2(i) := (i == left - 1) || is_green(i)` and `is_red2(i) := (i == right) || is_red(i)`, where `left` and `right` refer to the function's original parameters (inclusive-exclusive). These predicates can be used as the invariants, and are sufficient for showing that at the end of the loop the result is either the first red, or one-past-the-end if everything is green.)
An alternative is to tweak the invariants:
Let `left` and `right` be the function's original parameters (inclusive-exclusive), and let `l` (that's a lowercase L) and `r` be the variables used in the loop (exclusive-exclusive).
The original invariants are `is_green(l)` and `is_red(r)`, which require sneaky definitions when `l = left - 1` and `r = right`.
The tweaked invariants are `is_green(i) for all i where left <= i <= l` and `is_red(i) for all i where r <= i < right`. In other words, everything up to and including `l` is green, and everything from `r` onward is red.
These invariants are vacuously true when `l = left - 1` and `r = right`, so they hold before the loop (without having to define `left - 1` to be green and `right` to be red).
def binary_search(array, target):
left, right = 0, len(array)
while left < right:
middle = (left + right) // 2
if array[middle] < target:
left = middle + 1
else:
right = middle
return right
(Explanation: when `left` and `right` differ by 1, `(left + right) // 2` will return `left` and the search will not make any progress.)