劍指offer_11_旋轉數組中的最小數字

• 2019 年 10 月 6 日
• 筆記

如：{1,2,3,4,5}的一個旋轉數組為{3,4,5,1,2} 該數組的最小值為1

初看題目我們最直觀的解法並不難，遍曆數組用倆個"指針"一前以後，當前面"指針"指向的元素比後面的"指針"指向的數組元素小時，這時我們就找到旋轉數組中的最小元素，我們不難寫出如下程式碼：

public static int findMin(int[] arr) {      // 如果數組是只有一個元素 則不是旋轉數組同時也防止下邊的i+1越界      if(arr == null || arr.length <= 1){          return -1;      }        for (int i =0 ; i < arr.length -1; i++) {          if (arr[i] > arr[i + 1]) {              return arr[i + 1];          }      }      return -1;  }

但是上面這種方法當數組的元素特別多時，效率是比較低的，不足以拿到offer，現在考慮用二分法對上面演算法進行改良：

定義一個數組最左邊的"指針"left和一個數組最右邊的"指針"right，每次求倆個指針的中間值記為middle，如果left所對應的值要比middle小，那麼說明數組還在遞增中，最小值會在middle和right之間，這時候我們讓left等於middle，繼續用同樣的方式縮小範圍，如果middle要比right小，那麼說明最小值在left和middle之間，讓right等於middle，用同樣的方式繼續求下去，就能求到最小值啦。

public static int findMin(int []arr) {      int left = 0;      int right = arr.length;      while(left < right) {          int middle = (left + right) / 2;          if (arr[left] < arr[middle]) {              left = middle;          // 如果遇到相同的元素 我們就只能用遍歷了          } else if(arr[left] == arr[middle]){              for(int i = left; i <= middle; i++) {                  if(arr[i] < arr[middle]) {                      return arr[i];                  }              }              return arr[left];          } else{              right = middle;          }          if (right - left == 1) {              if(arr[right] > arr[left])                  return arr[left];              else                  return arr[right];          }      }      return  arr[left];  }

當left對應的元素與right對應的元素相等時，這是特殊情況，這裡選擇遍歷去找最小值。