Why does Binary search algorithm use floor and not ceiling - not in an half open range

Question

When we have an array with indexes from 0 to n for example. when I use the Binary search using floor or ceiling when calculating the middle index I get the same out put.

int middle = ceiling ((left+right)/2);

Is there a reason using floor over ceiling ? what bug will happen using the ceiling ?

Answer 1

This all depends on how you update your left and right variable.

Normally, we use left = middle+1 and right = middle-1, with stopping criteria left = right.

In this case, ceiling or flooring the middle value doesn't matter.

However, if we use left = middle+1 and right = middle, we must take the floor of the middle value, otherwise we end up in an endless loop.

Consider finding 11 in array 11, 22.

We set left = 0 and right = 1, the middle is 0.5, if we take the ceiling, it would be 1. Since 22 is larger than query, we need to cut the right half and move right boarder towards middle. This works fine when the array is large, but since there are only two elements. right = middle will again set right to 1. We have an infinite loop.

To sum up,

• both ceiling and flooring work fine with left = middle+1 and right = middle-1
• ceiling works fine with left = middle and right = middle-1
• flooring works fine with left = middle+1 and right = middle

Answer 2

There's no difference in complexity. Both variants are log(n).

Depending on the rest of your implementation, you may get a different result if your array looks for instance like

0 1 1 1 1 2

and looking for the index of a 1.

Answer 3

If you use the ceiling, this can result in an endless loop if just one element is left, because parting that range will still yield a one-element sequence. Still, you never need the middle element, so after comparison you can reduce the remaining range by that element, which will also cause the loop to terminate.