leetcode-旋转数组的最小数字

刷leetcode《剑指offer》中第十一题"旋转数组的最小数字",以下记录一下解题思路

题目

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

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

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

解析

方法一

1. 直接将数组进行排序，输出num[0]
2. 排序可以直接使用冒泡排序、快速排序、归并排序或者直接暴力循环破解
3. 再直接点使用库函数，直接Arrays.sort(arr)

方法二

1. 题目数组为半有序，使用二分查找，分而治之(减治思想)

2. 数组中最特殊的位置是左边位置 left 和右边位置 right，将它们与中间位置 mid 的值进行比较，进而判断最小数字出现在哪里。

3. • 用左边位置 left 和中间位置 mid 的值进行比较是否可以？

     举例：[3, 4, 5, 1, 2] 与 [1, 2, 3, 4, 5] ，此时，中间位置的值都比左边大，但最小值一个在后面，一个在前面，因此这种做法不能有效地减治。

     • 用右边位置 right 和中间位置 mid 的值进行比较是否可以？

       举例：[1, 2, 3, 4, 5]、[3, 4, 5, 1, 2]、[2, 3, 4, 5 ,1]，用右边位置和中间位置的元素比较，可以进一步缩小搜索的范围。

     

注意

当中间值与最右边的值作比较的时候，减少压缩范围，并不能去掉mid，因为mid有可能是最小的。

具体实现代码

class Solution {
    public int minArray(int[] numbers) {
        if (numbers.length == 0 || numbers == null){
            return 0;
        }
        // 二分查找，分而治之(旋转有序，使用二分)
        int left = 0,right = numbers.length-1;
        while (left < right){
            int mid = left + ( right - left) / 2;
            // 如果中间值大于最右边的值
            if (numbers[mid] > numbers[right]){
                left = mid + 1;
                // 如果中间值小于最右边的值
            }else if (numbers[mid] < numbers[right]){
                right = mid;
            }else {
                right--;
            }
        }
        return numbers[left];
    }
}