3 ms·
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 a
by 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 agoI believe half-open intervals is something C++ uses for std::lower_bound and std::upper_bound.
- thaumasiotes 5y agoHalf-open intervals are very common because they overlap perfectly.
- mark-r 5y agoUsing 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 agoThis 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]