> 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/).

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.

Yeah, zero is probably not the best thing to return if left == right; same with an all red interval. Wasn't thinking carefully enough when generalizing it, but I will fix.

Psst, if you use an inclusive-exclusive interval for the parameters and an exclusive-exclusive interval for the implementation (see my top-level comment), it becomes nicer and you can keep your original invariants. You just need `left -= 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)

This is equivalent* to @anonymoushn's version if you define `left = lo - 1` and `right = hi`.

*Equivalent except for the rounding in the division.

Very good. I also find the division rounding and symmetry in your implementation aesthetically appealing. I think I just instinctively reach for half-open intervals for reasons unrelated to this particular problem.

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.

I saw your comments above as well. I'm not 100% convinced that this is better; I actually like the three "edge cases" because I find that code/proof of correctness easier to understand. In your code, I have to break the analysis into two cases:

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.

Defining `left - 1` to be green `right` to be red can be thought of as "padding" the input to ensure that there is at least one green and one red, but I'll concede that it is sneaky.

(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).