2021/04/14
分析
这里只给出可以无脑使用二分模板的方法：
把这个旋转数组去掉最后一个元素(target)后，剩余的部分仍然是一个旋转数组(arr’)
原命题等价为：寻找 arr’ 中第一个小于 target 的元素。
用左闭右开 True/False 模板来做，当没有找到这个元素的时候，left 刚好指向的是 target。
实现
2020.4.14 rust 重做
impl Solution {
pub fn find_min(nums: Vec<i32>) -> i32 {
let mut i = 0;
let mut j = nums.len() - 1;
while i < j {
let mid = i + (j - i) / 2;
if nums[mid] <= nums[nums.len() - 1] {
j = mid;
} else {
i = mid + 1;
}
}
return nums[i];
}
}
2020.1.23 刚学二分时做的
class Solution {
static int search(int l, int r, Predicate<Integer> f) {
while (l < r) {
int m = l + (r - l) / 2;
if (f.test(m)) {
r = m;
} else {
l = m + 1;
}
}
return l; // 此时 l 等于 r，并且 f(l) 是第一个等于 true 的点
}
static int findMin(int[] array) {
int l = 0, r = array.length - 1;
// 第一个小于等于最右端的点的元素位置，即最小值
int index = search(l, r, m -> array[m] <= array[r]);
return array[index];
}
}
我自己的一开始写的分类讨论的版本，看起来还是比较乱的
class Solution {
public int findMin(int[] nums) {
int i = 0;
int j = nums.length - 1;
// 如果是升序的
if (nums[i] <= nums[j]) return nums[i];
while (true) {
if (i == j || i == j - 1) return nums[j];
int mid = (i + j) / 2;
int n = nums[mid], l = nums[i], r = nums[j];
if (n > l) { // n 在上方
if (nums[mid+1] > nums[mid]) {
i = mid + 1;
} else {
return nums[mid + 1];
}
} else { // n 在下方
if (nums[mid] > nums[mid - 1]) {
j = mid - 1;
} else {
return nums[mid];
}
}
}
}
}