3 ms·

So, in your implementation, you always reduce the search range to n - n/2 to avoid branches. Why can it not be always n/2 - seeing as you've just examined and r

So, in your implementation, you always reduce the search range to n - n/2 to avoid branches. Why can it not be always n/2 - seeing as you've just examined and ruled out your middle element? i.e. seeing as how n/2 >= (n-1)-(n-1)/2 ?

sereja 4y ago
This is a tricky part. The middle element is still part of the search range if we go "left" (≥). After we compare against it, the search range length becomes either floor(n/2) or ceil(n/2), in the latter case including the middle element (we will never compare against it again, but it still needs to be the first element of the search range). To avoid additional checks and branching, we can just always make the next search range length ceil(n/2), effectively adding that middle element to the search range in case we go "right" (<).