题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1
示例 2：

输入：[2,2,2,0,1]
输出：0

算法解析

首先还是得知道二分查找的核心思路是什么：

  1. int low = 0;
  2. int high = arrays.length;
  3. while(low <= high){
  4.     int mid = (low + high) >>> 1;
  5.     if(arrays[mid] < value){
  6.         low = mid + 1;
  7.     }else if(arrays[mid] > value){
  8.         high = mid - 1;
  9.     }else{
  10.         return mid;
  11.     }
  12. }

对于这个算法来说我们需要处理一些特殊的case

  1. 输入的数组没有重复的数字：[3,4,5,1,2]
  2. 输入的数组包含重复的数字：[3,4,5,1,2,2,2]

x与 y分别指向数组的两边，中间位置为m
1.当data[m]的值大于data[y]的值，说明最小值在[m+1, y]之间，这个时候x赋值为m+1；
2.当data[m]的值小于data[y]值，说明最小值在[x, mid]之间，这个时候y赋值为mid；
3.当data[m]的值等于data[y]值，说明最小值在[x, y]之间的位置；

算法实现

  1. class Solution {
  2.     public int minArray(int[] numbers) {
  3.         if(numbers == null){
  4.             return Integer.MAX_VALUE;
  5.         }
  6.         int low = 0;
  7.         int high = numbers.length - 1;
  8.         while(low < high){
  9.             int mid = (low + high)/2;
  10.             if(numbers[mid] > numbers[high]){
  11.                 low =mid + 1;
  12.             }else if(numbers[mid] > numbers[low]){
  13.                 high = mid;
  14.             }else{
  15.                 high--;
  16.             }
  17.         }
  18.         return numbers[low];
  19.     }
  20. }