0153.Find-Minimum-in-Rotated-Sorted-Array

題目

題目大意

解題思路

Big O

• 時間複雜 : O(logN)
• 空間複雜 : O(1)

來源

• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
• https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0153.Find-Minimum-in-Rotated-Sorted-Array/main.go

package findminimuminrotatedsortedarray

// 時間複雜 O(logN), 空間複雜 O(1)
func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        if nums[left] < nums[right] {
            return nums[left]
        }
        mid := int(uint(left+right) >> 1)
        if nums[mid] >= nums[left] {
            // mid 一定不是最小值了
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

Benchmark