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