旋转数组中查找最小值-剑指Offer11

标签：block   []   bin   顺序   ++   i++   数组   序列   一个   

1.题目简介

求一个旋转数组的最小值。（ 把一个数组从最开始的若干个元素搬到数组的末尾，即为旋转数组。）

• 输入：一个递增排序数组的旋转
• 输出：数组的最小值
• 例子：数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.

2.思路分析

最直观的解法是从头到尾顺序遍历，这种方法的时间复杂度为O(n)。这里并没有用到旋转数组的知识，显然不合题意。

结合提议，旋转数组从有序数组中的得来的，经过旋转后得到的两个部分也为有序的。在有序数组中查找首选二分法，可以把时间复杂度变为O(n)。由于是把递增数组中最开始的若干个元素移到末尾，那么经过旋转后，数组开头的元素一定是大于等于末尾的元素，这是循环的条件。

和二分法一样设置三个指针，low、mid和high，分别指向数组中的开头、中间和结尾元素。如果开头元素小于等于中间元素，证明前半部分是递增的，要找的最小值在后半部分，此时把low指向mid；同样的，如果中间元素的指小于等于最后元素的值，说明后面是递增序列，要找的元素在前半部分，把high指向mid。

那什么时候找到呢？当Low和high相邻时，且high所指的元素就时最小值。

例子：
arr = {3,4,5,1,2} ,low=0,high=4;mid=2;
经过依次查找，arr[low] 所以令low=mid=2；mid=3,第二次查找，arr[mid]=1，arr[high]=2，arr[mid] 所以令high = mid = 3;
由于low和high已经相邻，找到元素，跳出循环

注意：还要考虑两种特殊情况

3.代码

    /*用二分法，查找返回旋转数组的最小值，时间复杂度为O(n)*/
    public static int getMinOfRoateArray(int[] arr,int len) throws Exception {
        int min=0;
        int low = 0;
        int high = len - 1;
        int mid = low;
        if(arr==null||len==0) {
            throw new Exception("the array is illegal");
        }       
        while(arr[low]>=arr[high]) {
            if(high-low==1) { //相邻时候找到
                mid = high;
                break;
            }           
            mid = (low+high)/2;
            //特殊情况，中间 左右的值相等，只能顺序查找了
            if(arr[low]==arr[high] && arr[mid] == arr[low]) {
                min = arr[0];
                for(int i = 1 ; i 

4.相关-二分查找

//array为要排序的整型数组
/**非递归*/
    public int binarysearch(int x) {
        if(array.isEmpty()) {
            return -1;
        }
        int low = 0;
        int high = array.size()-1;
        
        while(low  array.get(high-1) ||low >high) {
            return -1;
        }
        if(x  array.get(mid)) {
            return binarySearchR(x,mid+1,high);
        }
        else {
            return mid+1;
        }
    }

旋转数组中查找最小值-剑指Offer11

标签：block   []   bin   顺序   ++   i++   数组   序列   一个   

原文地址：https://www.cnblogs.com/java-learner/p/9583705.html