LeetCode - Easy - 374. Guess Number Higher or Lower

逃离我推掉我的手 2023-01-10 10:26 96阅读 0赞

## Topic ##

*  Binary Search

## Description ##

[https://leetcode.com/problems/guess-number-higher-or-lower/][https_leetcode.com_problems_guess-number-higher-or-lower]

We are playing the Guess Game. The game is as follows:

I pick a number from `1` to `n`. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API `int guess(int num)`, which returns 3 possible results:

*  `-1`: The number I picked is lower than your guess (i.e. `pick < num`).
 *  `1`: The number I picked is higher than your guess (i.e. `pick > num`).
 *  `0`: The number I picked is equal to your guess (i.e. `pick == num`).  
    Return the number that I picked.

**Example 1**:

Input: n = 10, pick = 6
    Output: 6

**Example 2**:

Input: n = 1, pick = 1
    Output: 1

**Example 3**:

Input: n = 2, pick = 1
    Output: 1

**Example 4**:

Input: n = 2, pick = 2
    Output: 2

**Constraints**:

*  1 <= n <= 2³¹ - 1
 *  1 <= pick <= n

## Analysis ##

略

## Submission ##

class GuessGame { 
    	public static int pick;
    
    	public int guess(int num) { 
    		return pick == num ? 0 : pick < num ? -1 : 1;
    	}
    }
    
    public class GuessNumberHigherOrLower extends GuessGame { 
    
    	public int guessNumber(int n) { 
    		int left = 1, right = n;
    
    		while (left <= right) { 
    			int mid = left + (right - left) / 2;
    			int guess = guess(mid);
    
    			if (guess < 0)
    				right = mid - 1;
    			else if (guess > 0)
    				left = mid + 1;
    			else
    				return mid;
    		}
    
    		return -1;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class GuessNumberHigherOrLowerTest { 
    
    	@Test
    	public void test() { 
    		GuessNumberHigherOrLower obj = new GuessNumberHigherOrLower();
    
    		assertEquals(GuessGame.pick = 6, obj.guessNumber(10));
    		assertEquals(GuessGame.pick = 1, obj.guessNumber(1));
    		assertEquals(GuessGame.pick = 1, obj.guessNumber(2));
    		assertEquals(GuessGame.pick = 2, obj.guessNumber(2));
    	}
    }

[https_leetcode.com_problems_guess-number-higher-or-lower]: https://leetcode.com/problems/guess-number-higher-or-lower/