3 releases
0.0.4 | Nov 3, 2021 |
---|---|
0.0.3 | Nov 2, 2021 |
0.0.1 | Oct 22, 2021 |
#2244 in Algorithms
195KB
155 lines
Stalin Binary Search
Idea is based on Stalin Sort
It's alike binary search but any checking element which is not target one is eliminated.
Complexity is~ O(log n) on first run however after~ n/2 runs Complxity will be O(1) guaranteed. Should not fail on unsorted.
(there analysis not from Fingon but with pictures and fancy text targetting working of this on unsorted arrays The underlying analysis.)
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn find_on_sorted() {
let mut sorted = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
let find = sorted.stalin_find(3);
assert!(find.is_some());
assert_eq!(
find,
Some(1),
);
assert_eq!(
sorted,
vec![1, 3, 4, 6, 7, 8, 9],
);
if let Some(find_3) = find {
assert_eq!(
3, sorted[find_3]
);
}
}
#[test]
fn find_on_unsorted() {
let mut unsorted = vec![33, 55, 3, 4, 7657, 6, 7, 8];
assert_eq!(
unsorted.stalin_find(3),
Some(2),
);
assert_eq!(
unsorted,
vec![33, 55, 3, 7657, 7, 8],
);
if let Some(find_7) = unsorted.stalin_find(7) {
assert_eq!(
7, unsorted[find_7]
);
}
}
#[test]
fn find_fail() {
let mut unsorted = vec![33, 55, 3, 4, 7657, 6, 7, 8];
assert_eq!(
unsorted.stalin_find(77),
None,
);
assert_eq!(
unsorted,
vec![],
);
}
#[test]
fn find_not_fail() {
let mut unsorted = vec![33, 55, 3, 4, 7657, 6, 7, 8, 2];
assert_eq!(
unsorted.stalin_find(2),
Some(0),
);
assert_eq!(
unsorted,
vec![2],
);
}
}