文章目录
- 1. 题目
- 2. 题目解析
- 3. 代码
1. 题目
在线oj
2. 题目解析
解法一:暴力查找最小值
时间复杂度:0(N)
解法二:二分查找算法
- 【二段性】:
-
A~B:nums[i] > nums[i + 1]
-
C~D:nums[i] < nums[i + 1]
- 【解题思路】:
我们选择以D点的值作为参照物:
- nums[mid] > nums[n - 1] ----> left = mid + 1
- nums[mid] < nums[n - 1] ----> right = mid
3. 代码
class Solution {public int findMin(int[] nums) {int n = nums.length;int left = 0;int right = n - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > nums[n - 1]){left = mid + 1;}else {right = mid;}}return nums[left];}
}