題目描述

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。

示例 1：

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

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

解題思路

旋轉(zhuǎn)后的數(shù)組可以看成兩個有序數(shù)組，左邊是一個升序排列的數(shù)組，右邊也是一個升序排列的數(shù)組，因此，最左邊的數(shù)是左邊有序數(shù)組的最小值，最右邊數(shù)是右邊有序數(shù)組的最大值，通過二分法比較中間值與左右數(shù)組兩邊的值可以很快定位到最小值。

代碼

int minArray(int* numbers, int numbersSize){

    int start = 0, end = numbersSize - 1;
    int mid_index = 0;

    if(numbers == NULL || numbersSize == 0)
    {
        return 0;
    }

    while(start < end)
    {
        mid_index = (start + end) / 2;
        if(numbers[mid_index] < numbers[end])
            end = mid_index;
        else if(numbers[mid_index] == numbers[end])
            end--;
        else
            start = mid_index + 1;
    }

    return numbers[start];
}

測試代碼及結(jié)果

#include<stdio.h>
#include<stddef.h>

int minArray(int *numbers, int numbersSize);

int main(void)
{
    int res1, res2, res3, res4;
    int nums1[] = {3, 4, 5, 1, 2};
    int nums2[] = {3, 4, 4, 5, 5, 1, 2};
    int nums3[] = {3};
    void *nums4 = NULL;
    // 功能測試
    res1 = minArray(nums1, sizeof(nums1) / sizeof(int));
    printf("%d\n", res1);

    res2 = minArray(nums2, sizeof(nums2) / sizeof(int));
    printf("%d\n", res2);

    // 邊界值測試
    res3 = minArray(nums3, sizeof(nums3) / sizeof(int));
    printf("%d\n", res3);

    // 特殊輸入測試
    res4 = minArray(nums4, sizeof(nums4) / sizeof(int));
    printf("%d\n", res4);
}

執(zhí)行結(jié)果

時間復(fù)雜度：O(logn)，空間復(fù)雜度: O(1)。