猜數字大小（easy）
更好的閱讀體驗應該是：
- 審題-思考
- 答題
- 整理-歸納
一、題目
LeetCode：374.猜數字大小
猜數字游戲的規則如下：
每輪游戲，我都會從 1 到 n 隨機選擇一個數字， 請你猜選出的是哪個數字，
如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了，
你可以通過呼叫一個預先定義好的介面 guess(num) 來獲取猜測結果，回傳值一共有 3 種可能的情況（-1，1 或 0）：
- -1：我選出的數字比你猜的數字小 pick < num
- 1：我選出的數字比你猜的數字大 pick > num
- 0：我選出的數字和你猜的數字一樣，恭喜！你猜對了！pick == num
示例：
輸入：n = 10, pick = 6
輸出：6
要注意審題哦～
二、二分法解題
二分查找是一種基于比較目標值和陣列中間元素的教科書式演算法，
- 如果目標值等于中間元素，則找到目標值，
- 如果目標值較小，繼續在左側搜索，
- 如果目標值較大，則繼續在右側搜索，
基礎模版
- 確定初始的左右邊界:
left: 0right: nums.length-1mid: (left + (right - left) >> 1)
- 如果中間元素值
nums[mid]< target：證明中間值左側包括中間值都不符合要求，可以直接排除，left = mid + 1 - 如果中間元素值
nums[mid]：證明中間值右側包括中間值都不符合要求，可以直接排除，right = mid - 1 - 如果中間元素值
nums[mid]= target：直接回傳mid的下標 - 重新定義了左右邊界，也需要重新計算中間值，我們需要繼續進行范圍的排除
- 定義搜索的條件，應該是搜索區間都不為空，即
left <= right
本題與基礎模版的區別
- 我們的目標是尋找指定數字
- 判斷目標值大小的方法是
guess，它已經幫我們判斷了target > mid等價于guess(mid)回傳1target < mid等價于guess(mid)回傳-1target = mid等價于guess(mid)回傳0
Javasciprt 代碼
var guessNumber = function(n) {
let left = 0; // 初始左邊界
let right = n; // 初始右邊界
while (left <= right) {
var mid = left + Math.floor((right - left) / 2); //防止溢位
if (guess(mid) === 0) {
return mid;
} else if (guess(mid) === 1) {
// 目標值大于中值，則中間左側可以拋棄了
left = mid + 1;
} else {
// 目標值小于中值，則中間右側可以拋棄了
right = mid - 1;
}
}
return -1;
};
三、寫在最后
本文是二分查找-模版 I 的第四題，歇一歇，我們需要面對的下一題并不是單純的增序列了，不妨回到二分法的檔案去先了解下如何處理它，
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵～
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- JavaScript 版 LeetCode 題解
- 前端進階筆記
- CSDN
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233064.html
標籤：其他
上一篇：獲取小程式原始碼總結