模版 II-3 尋找旋轉排序陣列中的最小值（middle）
更好的閱讀體驗應該是：
- 審題-思考
- 答題
- 整理-歸納
:::
一、題目
153. 尋找旋轉排序陣列中的最小值
假設按照升序排序的陣列在預先未知的某個點上進行了旋轉，例如，陣列 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] ，
請找出其中最小的元素，
示例
輸入：nums = [4,5,6,7,0,1,2]
輸出：0
注意
- nums 中的所有整數都是 唯一 的
- nums 原來是一個升序排序的陣列，但在預先未知的某個點上進行了旋轉
- 最終目的是找到拐點，因為一個遞增序列的旋轉，拐點即最小
二、基礎模版 II
- 確定初始的左右邊界:
left: 0right: nums.length-1mid: (left + (right - left) >> 1)
- 查找條件需要訪問元素的直接右鄰居，
- 使用元素的右鄰居來確定是否滿足條件，并決定是向左還是向右，
- 保證查找空間在每一步中至少有 2 個元素，
- 需要進行后處理， 當你剩下 1 個元素時，回圈 / 遞回結束， 需要評估剩余元素是否符合條件，
三、題解
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = left + ((right - left) >> 1);
// 與nums[right]比較是因為，是遞增序列
if (nums[mid] > nums[right]) {
// 中間值 > 末尾 = 證明拐點在右側，遞增區間在左側，不用看左側了
left = mid + 1;
} else {
right = mid;
// 中間值 < 末尾 = 右側是遞增序列，右側較大的區間可以忽略
}
}
return nums[left];
};
四、寫在最后
本文是二分查找-模版 II 的最后一題，接下來我們將面對更大的挑戰，加油～
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- JavaScript 版 LeetCode 題解
- 前端進階筆記
- CSDN
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/236095.html
標籤：其他
上一篇：如何使用jq封裝tab切換