Approach
It has been a while since CMPSC121/122 at Penn State so I admittedly forgot about the iterative approach to binary search. After fussing with janky ways to get the recursive approach to work I was able to get this implemented.
Set l (left) to 1.
Set r (right) to n (size of search area).
Slowly close in from left to right on the number by checking mid.
So on each iteration, if mid is answer, great! Return it.
If the answer is higher than mid, we can ignore the left half of the search area and set our new l (left) to mid + 1.
Conversely, if the answer is lower than mid, we can ignore the right half of the search and set our new r (right) to mid - 1;
For example: n = 10, answer = 9
Iteration 1
l = 1 r = 10 mid = 5
answer > mid
Iteration 2
l = 6 r = 10 mid = 8
answer > mid
Iteration 3
l = 9 r = 10 mid = 9
answer == mid
Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Code
class Solution {
public:
int guessNumber(int n) {
int l = 1;
int r = n;
int mid;
while(l <= r){
mid = l + (r-l) / 2;
int g = guess(mid);
if(g == 0){
return mid;
}
if(g == 1){ // number is greater
l = mid + 1;
}
if(g == -1){ // number is less
r = mid - 1;
}
}
return -1;
}
};