题目
编程语言
rust
注意点
二分法
代码
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let mut left = 0_i32;
let mut right = (nums.len() as i32) - 1;
let mut mid;
while left <= right {
mid = left + ((right - left) >> 1);
if nums[mid as usize] == target {
return mid as i32;
}
match nums[mid as usize].cmp(&nums[left as usize]) {
// left和mid 落在同一数组中
std::cmp::Ordering::Greater | std::cmp::Ordering::Equal => {
// left,mid,right,target在同一数组中
if nums[mid as usize] > target && target >= nums[left as usize] {
right = mid - 1;
// target落在mid和right中间
}else if nums[mid as usize] < target || target < nums[left as usize] {
left = mid + 1;
}
},
// left和mid 落在两个数组中
std::cmp::Ordering::Less => {
// left,mid,right,target在同一数组中
if nums[mid as usize] < target && target <= nums[right as usize] {
left = mid + 1;
// target落在left和mid中间
}else if nums[mid as usize] > target || target > nums[right as usize] {
right = mid - 1;
}
},
}
}
-1
}
测试
#[cfg(test)]
mod tests{
use super::*;
#[test]
fn test_exist(){
assert_eq!(search(vec![4,5,6,7,0,1,2],0),4);
}
#[test]
fn test_not_exist1(){
assert_eq!(search(vec![4,5,6,7,0,1,2],3),-1);
}
#[test]
fn test_not_exist2(){
assert_eq!(search(vec![1],0),-1);
}
}