2021/04/12
用True/False 左闭右开模板
找最小的可以直接套模板，找最大的可以转化为「找第一个大于 target 的数」，然后看前一个数是不是 target
impl Solution {
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut res = vec![-1, -1];
let mut l = 0;
let mut r = nums.len();
while l < r {
let mut m = l + (r - l) / 2;
if nums[m] >= target {
r = m;
} else {
l = m + 1;
}
}
if l < nums.len() && nums[l] == target {
res[0] = l as i32;
}
let mut l = 0;
let mut r = nums.len();
while l < r {
let mut m = l + (r - l) / 2;
if nums[m] > target {
r = m;
} else {
l = m + 1;
}
}
if l > 0 && nums[l - 1] == target {
res[1] = (l - 1) as i32;
}
return res;
}
}
闭区间二分查找
impl Solution {
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut res = vec![-1, -1];
if nums.len() == 0 {
return res;
}
let mut l = 0 as i32;
let mut r = (nums.len() - 1) as i32;
while l < r {
let m = l + (r - l) / 2;
if nums[m as usize] == target {
r = m;
} else if nums[m as usize] > target {
r = m - 1;
} else {
l = m + 1;
}
}
if l < nums.len() as i32 && nums[l as usize] == target {
res[0] = l as i32;
}
let mut l = 0;
let mut r = nums.len() - 1;
while l < r {
let m = l + (r - l + 1) / 2;
if nums[m] == target {
l = m;
} else if nums[m] > target {
r = m - 1;
} else {
l = m + 1;
}
}
if l < nums.len() && nums[l] == target {
res[1] = l as i32;
}
return res;
}
}
二分找第一个，线性找最后一个
class Solution {
public int[] searchRange(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
// 二分结束
if (l == nums.length // 数组中没有满足性质的点
|| nums[l] != target // 满足性质的点并不是 target
) {
return new int[]{-1, -1};
}
// 此时 l 是第一个等于 target 的点
int l2 = l;
// 处理 l 已经是最后一个点的情况
for ( ; l2 < nums.length - 1 && nums[l] == nums[l2 + 1] ; l2++);
return new int[]{l, l2};
}
}