Binary search with confidence

Re:Binary search with confidence by OscarCunningham on Sunday March 06, 2022 @10:51PM (#30584056)

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

[ Parent | on HN ]

Re:Binary search with confidence by hddqsb on Monday March 07, 2022 @01:55PM (#30591803)

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

[ Parent | on HN ]

Re:Binary search with confidence by cleancoder0 on Monday March 07, 2022 @07:03AM (#30586759)

I believe half-open intervals is something C++ uses for std::lower_bound and std::upper_bound.

[ Parent | on HN ]

Re:Binary search with confidence by mark-r on Monday March 07, 2022 @11:20AM (#30589623)

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.

[ Parent | on HN ]

Re:Binary search with confidence by thaumasiotes on Monday March 07, 2022 @07:24AM (#30586927)

Half-open intervals are very common because they overlap perfectly.

[ Parent | on HN ]