Why low + 1?

[jhnns]

Hi,

thanks for sharing your bullet proof version of binary search 😉.

I still have a question: Why do you add +1 if the key couldn't be found? Given the haystack [1, 2, 4, 5] and the needle 3 I'd expect -2 as return value because 3 should be inserted at index 2.

[Deleted user]

Let's assume the algorithm returns -low, rather than -(low + 1).

Then, run the algorithm with these results:

> bs([1, 2, 4, 5], 0, cmp)
0
> bs([1, 2, 4, 5], 1, cmp)
0

Ack! Two completely different results (an item is not in the array, and an item is in the array) return exactly the same result! This means that you can't use a simple check (such as result < 0) to see if something is in the array or not; you'd have to check against the array as well.

We use -(low + 1) to get around this, making it so that if we find the desired item, a nonnegative result it returned, and if we don't, a negative result is returned.

TLDR: -0 and +0 represent the same number, so we need to disambiguate them somehow.

[jhnns]

Seems reasonable, thx! 👍
Could be mentioned in the docs 😉 .