[Solved] What’s wrong with this binary search? [closed]

Question

There are at least two, possibly three, things I can see wrong with it.

It uses (low + high)/2. The addition may overflow to a negative number if the array is very large. If so, division by 2 will lead to a negative index. This can be fixed by using (low + high)>>>1.

It is not documented. I am guessing that it is intended to return the match index if it finds the key in the array, and a negative value on miss. I am not sure exactly what the negative result is supposed to represent, due to the lack of documentation.

Depending on the missing specification, there may be additional problems.

Accepted Answer

There are at least two, possibly three, things I can see wrong with it.

It uses (low + high)/2. The addition may overflow to a negative number if the array is very large. If so, division by 2 will lead to a negative index. This can be fixed by using (low + high)>>>1.

It is not documented. I am guessing that it is intended to return the match index if it finds the key in the array, and a negative value on miss. I am not sure exactly what the negative result is supposed to represent, due to the lack of documentation.

Depending on the missing specification, there may be additional problems.