153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值_每日簡(jiǎn)訊
(資料圖片僅供參考)
已知一個(gè)長(zhǎng)度為 n 的數(shù)組，預(yù)先按照升序排列，經(jīng)由 1 到 n 次 旋轉(zhuǎn) 后，得到輸入數(shù)組。例如，原數(shù)組 nums = [0,1,2,4,5,6,7] 在變化后可能得到：若旋轉(zhuǎn) 4 次，則可以得到 [4,5,6,7,0,1,2]若旋轉(zhuǎn) 7 次，則可以得到 [0,1,2,4,5,6,7]注意，數(shù)組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉(zhuǎn)一次 的結(jié)果為數(shù)組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
給你一個(gè)元素值 互不相同 的數(shù)組 nums ，它原來(lái)是一個(gè)升序排列的數(shù)組，并按上述情形進(jìn)行了多次旋轉(zhuǎn)。請(qǐng)你找出并返回?cái)?shù)組中的 最小元素 。
你必須設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(log n) 的算法解決此問(wèn)題。
示例 1：
輸入：nums = [3,4,5,1,2]輸出：1解釋?zhuān)涸瓟?shù)組為 [1,2,3,4,5] ，旋轉(zhuǎn) 3 次得到輸入數(shù)組。示例 2：
輸入：nums = [4,5,6,7,0,1,2]輸出：0解釋?zhuān)涸瓟?shù)組為 [0,1,2,4,5,6,7] ，旋轉(zhuǎn) 4 次得到輸入數(shù)組。示例 3：
輸入：nums = [11,13,15,17]輸出：11解釋?zhuān)涸瓟?shù)組為 [11,13,15,17] ，旋轉(zhuǎn) 4 次得到輸入數(shù)組。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums 中的所有整數(shù) 互不相同nums 原來(lái)是一個(gè)升序排序的數(shù)組，并進(jìn)行了 1 至 n 次旋轉(zhuǎn)
來(lái)源：力扣（LeetCode）鏈接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
func findMin(nums []int) int { left, right := -1, len(nums)-1 // 開(kāi)區(qū)間 (-1, n-1) for left+1 < right { // 開(kāi)區(qū)間不為空 mid := left + (right-left)/2 if nums[mid] < nums[len(nums)-1] { // 藍(lán)色 right = mid } else { // 紅色 left = mid } } return nums[right]}
標(biāo)簽：
