34. Find First and Last Position of Element in Sorted Array
寻找一个Vec的target的左右边界index
思路：
有序阵列加上题目要求O(log n)
几乎等于逼你用二元搜寻树
我建立两个搜寻树找左右边界
往左找跟往右找的差别在于left right mid每次循环往哪边偏
像往左是let mid = left + (right - left) / 2;
而往右是let mid = left + (right - left + 1) / 2;
往右会让mid每次+1再/2 会比较靠右 避免无限循环TLE
left right也是一样原理
Code:
impl Solution {
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
if nums.is_empty() {
return vec![-1, -1];
}
let left = Self::find_left_boundary(&nums, target);
let right = Self::find_right_boundary(&nums, target);
vec![left, right]
}
pub fn find_left_boundary(nums: &Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] < target {
left = mid + 1;
} else {
right = mid;
}
}
if nums[left] == target {
left as i32
} else {
-1
}
}
pub fn find_right_boundary(nums: &Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
let mid = left + (right - left + 1) / 2;
if nums[mid] > target {
right = mid - 1;
} else {
left = mid;
}
}
if nums[left] == target {
left as i32
} else {
-1
}
}
}

大师