Why does binary search algorithm use floor and not ceiling - not in half-open range
If we have an array with indices from 0 to n, for example. when i use a binary search using floor or ceiling when calculating the average index i get the same output.
int middle = ceiling ((left + right) / 2);
Is there a reason to use a floor above the ceiling? what error will happen from the ceiling?
source to share
It depends on how you update the variable left
and right
.
We usually use left = middle+1
it right = middle-1
with stop criteria left = right
.
In this case, the ceiling or floors of average value do not matter.
However, if we use left = middle+1
and right = middle
, we must take the mean word, otherwise we end up in an infinite loop.
Consider searching 11
an array 11, 22
.
Put left = 0
and right = 1
, in the middle 0.5
, if we take the ceiling, it will be 1
. Since it is 22
larger than the query, we need to cut the right half and move the right edge towards the middle. This works great when the array is large, but since there are only two elements. right = middle
will re-install right
in 1
. We have an endless loop.
Summarizing,
- both ceiling and flooring work great with
left = middle+1
andright = middle-1
ceiling - works great with
left = middle
andright = middle-1
- the flooring works great with
left = middle+1
andright = middle
source to share
If you are using a ceiling, it can end up in an infinite loop if there is only one element left, since dividing that range will still give a singleton sequence. However, you never need the middle element, so after the comparison, you can reduce the remaining range with that element, which will also end the loop.
source to share