-
Notifications
You must be signed in to change notification settings - Fork 45
/
mod.rs
76 lines (67 loc) · 2.29 KB
/
mod.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/// Search in sorted sequences by checking the next position based on an
/// linear interpolation of the search key.
///
/// # Parameters
///
/// * `arr`: Slice to search in.
/// * `target`: Object to search for.
///
/// # Notes
///
/// Since interpolations only be applied on numeric types, we choose `i32` to
/// avoid overkilling. If you desire a full functional trait of numeric types,
/// [num][1] crate would meet your needs.
///
/// [1]: https://github.com/rust-num/num
pub fn interpolation_search(arr: &[i32], target: &i32) -> Result<usize, usize> {
// 1. Handle empty sequence.
if arr.is_empty() {
return Err(0);
}
// 2. Setup variable storing iteration informaion.
// hi -> upper bound of search range.
// lo -> lower bound of search range.
// interpolant -> position to probe in the sequence
let mut hi = arr.len() - 1;
let mut lo = 0_usize;
let mut interpolant = 0_usize;
// 3. Main loop to calculate the interpolant.
loop {
let lo_val = arr[lo];
let hi_val = arr[hi];
// 3.1. Three condition to exit the loop
// a. hi and lo flag overlapping -> all elements are scanned.
// b. target value is less than the lowest value
// c. target value exceeds the highest value
if hi <= lo || *target < lo_val || *target > hi_val {
break;
}
// 3.2. The linear interpolation part
let offset = (*target - lo_val) * (hi - lo) as i32 / (hi_val - lo_val);
interpolant = lo + offset as usize;
let mid_val = arr[interpolant];
// 3.3. Comparison between the interpolant and targert value.
// New boundaries must step one index further to avoid infinite searching.
if mid_val > *target {
hi = interpolant - 1;
} else if mid_val < *target {
lo = interpolant + 1;
} else {
break;
}
}
// 4. Determine whether the returning interpolant equals to target value.
// `Result::Err` here maps to a position safe to insert while remains ordering.
if *target > arr[hi] {
Err(hi + 1)
} else if *target < arr[lo] {
Err(lo)
} else {
Ok(interpolant)
}
}
#[cfg(test)]
mod base {
use super::*;
sorted_no_duplicate_cases!(interpolation_search);
}