374. Guess Number Higher or Lower

Source link: https://leetcode.com/problems/guess-number-higher-or-lower/

Design

This problem could be solved by a simple binary search, which drop the left part of the array while the guessing number is smaller than the actual number, and vice versa.

Implementation

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return          -1 if num is lower than the guess number
 *                  1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
  public int guessNumber(int n) {
    int left = 1, right = n;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (guess(mid) == -1) {
        right = mid - 1;
      } else if (guess(mid) == 1) {
        left = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }
}

Complexity Analysis

Time: $O(logn)$

Space: $O(1)$