#search #binary #algorithm #element #fail #target #complexity #idea

stalin-binary-search

alike binary search but any checking element which is not target one is eliminated

3 releases

Uses new Rust 2021

0.0.4 Nov 3, 2021
0.0.3 Nov 2, 2021
0.0.1 Oct 22, 2021

#782 in Algorithms

AGPL-3.0-only

195KB
155 lines

Rust crates.io version

Stalin Binary Search

Idea is based on Stalin Sort ss

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],
    );
  }
}

No runtime deps