旋转数组的最小值

1 题目

将一个数组最开始的若干元素搬到数组的末尾，称之为数组的旋转。输入一个已排好序数组的一个旋转，求该旋转数组的最小元素。如，数组{3，4，，5，1，2}为有序数组{1，2，3，4，5}的一个旋转数组，该数组的最小值为1。

2 思路

2.1 思路1

暴力遍历数组，求出数组的最小元素。

时间复杂度：O(n)
空间复杂度：O(1)

2.2 思路2

将旋转后的数组看成两个升序的子序列，即查找一个元素（使用二分查找法），满足的条件为比相邻左边的元素小，也比相邻右边的元素小（如果存在的话）。

算法1详细（方便理解）：

• 用l指针指向第一个序列的第一个元素，用r指针指向第二个序列的最后一个元素；

• • 当l = mid时，r为最小元素（特殊处理当最小元素位于末尾的情况），例如{2,3,4,5,1}，此时最小元素为r指向的元素，而不是mid指向的元素;
• • 当元素满足比左边元素小，比右边元素小时，即为最小元素；
• • 如果中间指针mid（(l+r)/2）在第一个序列中（即A[mid] < A[l]），则要寻找的元素在后半段中，把l改为mid；
• • 如果中间指针mid第二个序列中(即A[mid]<A[r])，则要寻找的元素在前半中;

• 当l=r时，返回最小元素A[r]；否则，返回最小元素A[mid]。

算法2详细（上一种算法的改进版本）：

• 用l指针指向第一个序列的第一个元素，用r指针指向第二个序列的最后一个元素；

• • 如果中间指针mid（(l+r)/2）在第一个序列中（即A[mid] < A[l]），则要寻找的元素在后半段中，把l改为mid；
• • 如果中间指针mid第二个序列中(即A[mid]<A[r])，则要寻找的元素在前半中。

• 当l和r相邻时（此时mid=l），最小元素在r指向的元素。

时间复杂度：O(logn)
空间复杂度：O(1)

例如：原数组{1，2，3，4，5}，
旋转后的数组{2，3，4，5，1}，1比左边的5小，无右边的元素；
旋转后的数组{3，4，5，1，2}，1比左边的5小，比右边2小；
旋转后的数组{4，5，1，2，3}，1比左边的5小，比右边2小。

3 实现

3.1 暴力

#include<cstdio>

int solution(int *A, int n){
    int ans = A[0];
    for(int i = 1;i < n;i++)
        if(A[i] < ans) ans = A[i];
    return ans;
}

int main(){
    
    int A[] = {2,3,4,5,1};
    //int A[] = {3,4,5,1,2};
    //int A[] = {4,5,1,2,3};
    //int A[] = {5,1,2,3,4};
    
    printf("%d", solution(A, sizeof(A)/sizeof(A[0])));
    return 0;
}

3.2 二分查找

#include<cstdio>

int solution(int *A, int n){
    int l = 0, r = n - 1, mid;
    while(l <= r){
        mid = (l + r)/2;
        printf("值   %d %d %d \n", A[l], A[mid], A[r]);
        printf("序号 %d %d %d \n", l, mid, r);
        
        //特殊处理最小元素位于最后一个的情况，例如2,3,4,5,1的情况，此时mid=l=3,r=4
        if(l == mid && A[r] < A[mid]) break;
        
        //如果比左边相邻的元素小
        //同时也比右边相邻的元素小（如果右边元素不存在，则和自己比较）
        if((A[mid] < A[mid-1] && A[mid] <= A[mid+1])
        ) break;
        
        if(A[mid] < A[r]) r = mid;
        else l = mid;
    }
    return (l == mid)?A[mid+1]:A[mid];
}

int solution2(int *A, int n){
    int l = 0, r = n - 1, mid;
    while(A[l] >= A[r]){
        if(r -l ==1){
            mid = r;
            break;
        }
        mid = (l + r)/2;
        printf("值   %d %d %d \n", A[l], A[mid], A[r]);
        printf("序号 %d %d %d \n", l, mid, r);
        
        if(A[mid] < A[r]) r = mid;
        else l = mid;
    }
    return A[mid];
}

int main(){
    
    int A[] = {2,3,4,5,1};
    //int A[] = {3,4,5,1,2};
    //int A[] = {4,5,1,2,3};
    //int A[] = {5,1,2,3,4};
    
    printf("%d", solution(A, sizeof(A)/sizeof(A[0])));
    return 0;
}