给定一个长度为n的非降序排列的整数数组,和一个目标值 。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 ,返回 [-1, -1]
该题有的解法
[4,7,7,8,8,10],8
[3,4]
可以在数组中找到整数8,其开始位置为3,结束位置为4
[4,7,7,8,8,10],6
[-1,-1]
不可以在数组中找到整数6,故输出整数-1
struct Solution{ } use std::cmp::Ordering::{Less, Equal, Greater}; impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型一维数组 */ pub fn searchRange(&self, nums: Vec<i32>, target: i32) -> Vec<i32> { // write code here vec![ Self::floor(&nums, [-1, nums.len() as i32 - 1], target), Self::ceil(&nums, (-1, nums.len() as i32), target) ] } fn floor(v: &Vec<i32>, [l, r]: [i32; 2], t: i32) -> i32 { // (l, r] if l >= r {return -1} let mid = (l + 1) + (r - l - 1) / 2; // if mid < 0 {} match t.cmp(&v[mid as usize]) { Less => Self::floor(v, [l, mid - 1], t), Greater => Self::floor(v, [mid, r], t), Equal => { let r = Self::floor(v, [l, mid - 1], t); if r == -1 { mid } else {r} } } } fn ceil(v: &Vec<i32>, (l, r): (i32, i32), t: i32) -> i32 { // (l, r) if r - l < 2 { return -1 } let mid = (l + r)/2; match v[mid as usize].cmp(&t) { Greater => Self::ceil(v, (l, mid), t), Less => Self::ceil(v, (mid, r), t), Equal => { let r= Self::ceil(v, (mid, r), t); if r == -1 {mid} else {r} } } } }