Rust的已排序队列折半查找
已排序队列,折半查找。
这里是i32队列,复杂队列以后空了扩展
fn main() {
let mut v = Vec::new();
for pat in 1..2000 {
v.push(pat)
}
println!("Vec::{:?}", v);
let c = find_with_if(721, 0, (v.len()-1) as i32, &v);
println!("721 角标是: {:?}", c);
//
let c1 = find_with_if(234, 0, (v.len()-1) as i32, &v);
println!("234 角标是: {:?}", c1);
//
let c1 = find_with_match(513, 0, (v.len()-1) as i32, &v);
println!("513 角标是: {:?}", c1);
}
// 在排好序的数组中找到给定值
// x: i32 要找的值
// s: i32 查找起点角标
// e: i32 查找终点角标
// l: &Vec<i32> &数组 借用的队列
// 如果能 约定对比大小相等可以查找任何类型的数组
fn find_with_if(x: i32, s: i32, e: i32, l: &Vec<i32>) -> i32{
if s == e {
println!("Vec--S::{:?}-->E::{:?} 起点终点一致错误!", s, e);
return 0;
}
// 给定起点终点的中间点
let mid_point: i32 = (e - s) / 2;
// 该点的角标值
let mid_idx: usize = (s + mid_point) as usize;
// 输出信息方便查看
println!("Vec--S::{:?}-->E::{:?} Vec[{:?}]={:?}", s, e, mid_idx, l[mid_idx]);
// 三种情况,再递归,可以macth优化
if l[mid_idx] == x{
return mid_idx as i32;
}
else if l[mid_idx] > x {
return find_with_if(x, s, mid_idx as i32, l);
}
else if l[mid_idx] < x {
return find_with_if(x, mid_idx as i32, e, l);
}
//按理以上情况均可以处理了。但是这里还是 0 表达式防止编译错误
0
}
// 在排好序的数组中找到给定值
// x: i32 要找的值
// s: i32 查找起点角标
// e: i32 查找终点角标
// l: &Vec<i32> &数组 借用的队列
// 如果能 约定对比大小相等可以查找任何类型的数组
fn find_with_match(x: i32, s: i32, e: i32, l: &Vec<i32>) -> i32{
if s == e {
println!("Vec--S::{:?}-->E::{:?} 起点终点一致错误!", s, e);
return 0;
}
// 给定起点终点的中间点
let mid_point: i32 = (e - s) / 2;
// 该点的角标值
let mid_idx: usize = (s + mid_point) as usize;
// 输出信息方便查看
println!("Vec--S::{:?}-->E::{:?} Vec[{:?}]={:?}", s, e, mid_idx, l[mid_idx]);
// 三种情况,再递归,macth优化
match l[mid_idx] {
n if n == x => return mid_idx as i32,
n if n > x => return find_with_match(x, s, mid_idx as i32, l),
n if n < x => return find_with_match(x, mid_idx as i32, e, l),
_ => return 0,
};
}