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'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
我們來玩一個(gè)猜數(shù)游戲蒿褂，游戲規(guī)則是這樣的：我從1~n中選擇一個(gè)數(shù)，你需要猜我選的數(shù)是哪一個(gè)，如果你猜錯(cuò)的話死讹，我就會(huì)告訴你你猜的數(shù)比我選擇的數(shù)大還是小岂却，你可以調(diào)用一個(gè)API guess(int num) 泉唁，返回三個(gè)可能的結(jié)果雷酪，-1表示比我的數(shù)小捂龄，1表示比我的數(shù)大释涛，0表示猜中了。
這個(gè)問題用二分查找即可倦沧，重點(diǎn)只在于確定查找的范圍
For example
n = 10, I pick 6.
Return 6.
My Solution
(Java) Version 1 Time: 1ms:
用兩個(gè)變量來表示上界和下界唇撬，每次都猜測(cè)范圍1/2位置的數(shù)，然后根據(jù)返回的大小關(guān)系確定新的邊界刀脏，踩過的坑是局荚，如果直接用(up - down) / 2 + down來確定中間的數(shù)，那么將永遠(yuǎn)不會(huì)查找到作為邊界的兩個(gè)數(shù)愈污，第二坑是我本來想用0~n+1來把邊界的兩個(gè)數(shù)放進(jìn)范圍里，但是果然測(cè)試?yán)锩嬗衖nt的最大值轮傍，這就意味著n+1之后會(huì)溢出暂雹，所以只好在一開始單獨(dú)對(duì)邊界進(jìn)行判斷。
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public int guessNumber(int n) {
if(n == 1)return 1;
else if(guess(n) == 0)return n;
int down = 0, up = n;
int key = (up - down) / 2;
int flag = guess(key);
while(flag != 0){
if(flag == 1){
down = key;
key = (up - down) / 2 + down;
flag = guess(key);
}else{
up = key;
key = (up - down) / 2 + down;
flag = guess(key);
}
}
return key;
}
}
(Java) Version 2 Time: 1ms (By LeetCode):
* 來自官方的解答创夜，二分查找杭跪，寫法比我的高明得多，起碼邊界問題在循環(huán)中解決了，我第一時(shí)間沒有想到的是解答中的循環(huán)條件……
時(shí)間復(fù)雜度為O(log2n)
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public int guessNumber(int n) {
int low = 1;
int high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
}
(Java) Version 3 Time: 1ms (By LeetCode):
來自官方的解答涧尿，三分查找
In Binary Search, we choose the middle element as the pivot in splitting. In Ternary Search, we choose two pivots (say m1 and m2) such that the given range is divided into three equal parts. If the required number numnum is less than m1 then we apply ternary search on the left segment of m1. If numnum lies between m1 and m2, we apply ternary search between m1 and m2. Otherwise we will search in the segment right to m2.
簡單來說就是我們?cè)诙植檎业臅r(shí)候把數(shù)平均分為兩部分系奉，在三分查找中我們把數(shù)平均分為三部分
時(shí)間復(fù)雜度為O(log3n)
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public int guessNumber(int n) {
int low = 1;
int high = n;
while (low <= high) {
int mid1 = low + (high - low) / 3;
int mid2 = high - (high - low) / 3;
int res1 = guess(mid1);
int res2 = guess(mid2);
if (res1 == 0)
return mid1;
if (res2 == 0)
return mid2;
else if (res1 < 0)
high = mid1 - 1;
else if (res2 > 0)
low = mid2 + 1;
else {
low = mid1 + 1;
high = mid2 - 1;
}
}
return -1;
}
}
