題目位址:
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
尋找旋轉數組中的最小值。題目可以轉述為,尋找數組中從左向右第一個小于等于
nums[len - 1]
的數。可以利用二分法。
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int l = 0, r = nums.length - 1;
int len = nums.length;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] <= nums[len - 1]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}
}
時間複雜度 O ( log n ) O(\log n) O(logn)。