Binary Search
Table of Contents
1. Binary Search
A large question is how do we update left and right. This depends on whether we are searching for the maximum value or the minimum value.
If we are searching for the maximum value, then it makes sense to continuously search towards the right. Therefore, we should update left if the
midpoint is less than or equal to the query value.
On the other hand, if we are searching for the minimum value, then it makes sense to continuously search towards the left. Therefore, we should right if the midpoint is greater than or equal to the query value.
1.1. Off by One Error
If we're updating left, then if we set the midpoint equivalent to (left + right) / 2 there will be a moment where we have an
infinite loop. Therefore, the correct midpoint equation is actually (left + right + 1) / 2.