Description

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

Answer & Explaining

#include <stdio.h>
int findMin(int* nums, int numsSize) {
    int left = 0;  // 初始化左pointer，指向陣列的起始位置
    int right = numsSize - 1;  // 初始化右pointer，指向陣列的結束位置

    // 當左pointer小於右pointer時，進行二分查找
    while (left < right) {
        // 計算中間索引
        int mid = left + (right - left) / 2;

        // 如果中間值大於右pointer的值，說明最小值在右半部分
        if (nums[mid] > nums[right]) {
            left = mid + 1;  // 移動左pointer到中間索引的右邊
        } else {
            // 如果中間值小於或等於右pointer的值，最小值在左半部分或為中間值
            right = mid;  // 移動右pointer到中間索引
        }
    }

    // 當左右pointer重合時，返回最小值
    return nums[left];
}

Teating

#include <stdio.h>
int findMin(int* nums, int numsSize) {
    int left = 0;  // 初始化左pointer，指向陣列的起始位置
    int right = numsSize - 1;  // 初始化右pointer，指向陣列的結束位置

    // 當左pointer小於右pointer時，進行二分查找
    while (left < right) {
        // 計算中間索引
        int mid = left + (right - left) / 2;

        // 如果中間值大於右pointer的值，說明最小值在右半部分
        if (nums[mid] > nums[right]) {
            left = mid + 1;  // 移動左pointer到中間索引的右邊
        } else {
            // 如果中間值小於或等於右pointer的值，最小值在左半部分或為中間值
            right = mid;  // 移動右pointer到中間索引
        }
    }

    // 當左右pointer重合時，返回最小值
    return nums[left];
}

int main() {
    // 測試範例1
    int nums1[] = {3, 4, 5, 1, 2};  // 已旋轉的排序陣列
    int numsSize1 = sizeof(nums1) / sizeof(nums1[0]);  // 計算陣列大小
    printf("最小值: %d\n", findMin(nums1, numsSize1));  // 預期輸出: 1

    // 測試範例2
    int nums2[] = {4, 5, 6, 7, 0, 1, 2};  // 已旋轉的排序陣列
    int numsSize2 = sizeof(nums2) / sizeof(nums2[0]);  // 計算陣列大小
    printf("最小值: %d\n", findMin(nums2, numsSize2));  // 預期輸出: 0

    // 測試範例3
    int nums3[] = {11, 13, 15, 17};  // 未旋轉的排序陣列
    int numsSize3 = sizeof(nums3) / sizeof(nums3[0]);  // 計算陣列大小
    printf("最小值: %d\n", findMin(nums3, numsSize3));  // 預期輸出: 11

    return 0;
}