Leetcode skimming ---374

subject ： The rules of the number guessing game are as follows ： Every round of the game , I'll start from  1  To  n Randomly choose a number . Please guess which number is chosen . If you guessed wrong , I'll tell you , Is your guess larger or smaller than the number I selected . You can call a predefined interface int guess(int num) To get a guess , The total number of return values is 3 A possible situation （-1,1  or 0）：

-1： The number I picked is smaller than your guess         pick < num
1： The number I picked was bigger than you guessed           pick > num
0： I picked the same number as you guessed . Congratulations ！ You guessed it ！pick == num
Back to the number I picked .

Input ：n = 10, pick = 6

Output ：6

Method 1 ： Two points search

class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) {  //  Cycle until the left and right breakpoints of the interval are the same 
            int mid = left + (right - left) / 2;    //  Prevent overflow during calculation 
            if (guess(mid) <= 0) {
                right = mid;    //  The answer is in the interval  [left, mid] in 
            } else {
                left = mid + 1; //  The answer is in the interval  [mid+1, right] in 
            }
        }
        //  At this time there is  left == right,  The interval is reduced to a point , Is the answer 
        return left;
    }
};

Complexity analysis

Time complexity ：O(logn)

Spatial complexity ：O(1)