剑指offer--面试题11. 旋转数组的最小数字

深藏阁楼爱情的钟 2023-02-19 01:29 15阅读 0赞

## 题目描述 ##

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[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.  `numbers[high] > numbers[mid]`时，**high=mid**
2.  `numbers[high] < numbers[mid]`时，**low=mid+1**
3.  `numbers[high] = numbers[mid]`时，出现这种情况的`numbers`数组类似 \[1,0,1,1,1\] 或者\[1,1,1,0,1\]，不能判断最小值在mid左边还是右边

但是要注意一个问题，第一种情况下，`high = mid-1`会把最小值错过，所以`high=mid`

还有一个要注意，比较`numbers[high]` 和 `numbers[mid]` 的值，不要同时比较`high、mid、low`三个位置上的`numbers`值

## 解决方法 ##

class Solution {
        
        public int minArray(int[] numbers) {
        
            int low=0, high=numbers.length-1;
            while(low < high){
        
                int mid = (low+high) / 2;
                if( numbers[high] > numbers[mid]){
        
                    high = mid;  //注意若high=mid-1,可能错过最小值
                }else if(numbers[mid] > numbers[high]){
        
                    low = mid + 1;
                }else{
          //这种情况不好判断最小值在mid左边还是右边，只能一个个试
                    high--;
                }
            }
            return numbers[low];
        }
    }