一、尋找旋轉(zhuǎn)排序數(shù)組中的最小值

• 旋轉(zhuǎn)后的數(shù)組：分為兩段，都是升序的

  • 第一段的第一個(gè)元素比第二段任何一個(gè)都要大

• 尋找最小值

  • 實(shí)際上：尋找第二段的第一個(gè)元素，也即是原數(shù)組的翻轉(zhuǎn)點(diǎn)

• 利用二分法，將第二段第一個(gè)元素作為目標(biāo)target

  • 當(dāng)中間元素值小于target，則區(qū)間應(yīng)該改為中間元素的左邊
    • 因?yàn)榈诙蔚牡谝粋€(gè)元素可能在左邊，右邊值更大舍棄，right = center - 1
  • 當(dāng)大于等于時(shí)，區(qū)間改為中間元素的右邊
    • 因?yàn)楫?dāng)前的中間元素是屬于第一段的，應(yīng)該到右邊找第二段的第一個(gè)元素，left = center + 1
  • 不難看出，最后left指針會(huì)指向第二段的第一個(gè)元素
    • 但如果第二段不存在，即翻轉(zhuǎn)次數(shù)為數(shù)字長(zhǎng)度的整數(shù)倍時(shí)，最小值應(yīng)為第一段的最小值，left下標(biāo)對(duì)數(shù)組長(zhǎng)度取余即可

• class Solution {
      public int findMin(int[] nums) {
          //二分法尋找第二段的最小值，也即是翻轉(zhuǎn)點(diǎn)
          int left = 0;
          int right = nums.length - 1;
          int target = nums[0];//第一段升序數(shù)組的最小值
          while(left <= right) {
              int center = left + (right - left) / 2;
              if(nums[center] >= target) {//中間元素的值比第一段的第一個(gè)值大
                  left = center + 1;//翻轉(zhuǎn)點(diǎn)在中間指針的左邊
              } else {
                  right = center - 1;
              }
          }
          return nums[left % nums.length];
      }
  }
  

二、尋找峰值

• 數(shù)組中的任何給定序列視為交替的升序和降序序列

  • 符合二分有序的要求

• 從數(shù)組 nums 中的區(qū)間找到中間的元素 mid

  • 若該元素恰好位于降序序列或者一個(gè)局部下降坡度中（ nums[i] <= nums[i + 1] )，則說(shuō)明峰值會(huì)在本元素的左邊
    • 將搜索空間縮小為 midmid 的左邊(包括其本身)
  • 若該元素恰好位于升序序列或者一個(gè)局部上升坡度中（ nums[i] > nums[i + 1] )，則說(shuō)明峰值會(huì)在本元素的右邊
    • 將搜索空間縮小為 midmid 的右邊
  • 重復(fù)上述過(guò)程
  • 不斷地縮小搜索空間，直到搜索空間中只有一個(gè)元素，該元素即為峰值元素

• nums[-1] = nums[n] = -∞：只要數(shù)組中存在一個(gè)元素比相鄰元素大，那么沿著它一定可以找到一個(gè)峰值

  這個(gè)可以用反證法，如果這句不成立，比如mid 的元素大于mid +1，那么左邊一定有峰值。如果沒(méi)有，你從mid -1，開(kāi)始往前推，會(huì)發(fā)現(xiàn)，要保證這點(diǎn)，就會(huì)出現(xiàn)元素0>1>2>...>mid -2>mid-1>mid。即使這樣，由于-1是無(wú)窮小，那么0這個(gè)點(diǎn)也是峰值

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}