劍指Offer——旋轉數組的最小數字（JS實作）

題目描述

解題思路（序列化）

• 我剛開始看到本題，我發現找到比數組第一個元素小的第一個元素傳回不就行了，沒找到就傳回第一個，沒想到竟然成功AC
• 看了題解後，采用了二分查找的思想，第一個指針指向第一個元素，第二個指針指向最後一個元素，當中位數大于最右邊的元素，說明目标元素還在中位數的右邊，我們的目标元素就是最小的那個值，此時令left = mid + 1,如果中位數小于最右邊的元素，那麼這個中位數有可能為目标元素，令right = mid;如果中位數等于最右邊的元素，令right--;
• 循環結束，left下标對應的元素就應當是最小的元素，傳回即可。

序列化代碼

var minArray = function(numbers) {
    let left = 0;
    let right = numbers.length - 1;
    // ! 我們的目标：讓左右指針都指向最小的那個元素，然後終止循環
    while (left < right) {
        const mid = left + right >>> 1;
        if (numbers[mid] > numbers[right]) {
            // 如果中位數比最右邊的大，說明目标元素還在中位數右邊
            left = mid + 1;
        } else if (numbers[mid] < numbers[right]) {
            // 如果中位數比最右邊的小
            right = mid;
        } else {
            right--;
        }
    }
    return numbers[left];
};
      

總結（本題給我們的啟示思路）

• 啟示一：學會使用零填充右移1位的方法來求中位數
• 啟示二：學會使用二分查找的思想來找到最小值