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.

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

You might also like...

A simple implementation of the astar pathfinding algorithm from red blob games

A simple implementation of the astar pathfinding algorithm from red blob games. In order to use the pathfinder you must have a path map for it to navi

6 Nov 22, 2022

nsga is an opinionated implementation of the NSGA-II (Non-dominated Sorting Genetic Algorithm)

nsga nsga is an opinionated implementation of the NSGA-II (Non-dominated Sorting Genetic Algorithm), a multi-objective genetic optimization algorithm.

8 Oct 1, 2022

Fast, parallel, extensible and adaptable genetic algorithms framework written in Rust

oxigen Oxigen is a parallel genetic algorithm framework implemented in Rust. The name comes from the merge of OXIdación (Rust translated to Spanish) a

146 Dec 18, 2022

darwin-rs, evolutionary algorithms with rust

darwin-rs This library allows you to write evolutionary algorithms (EA) using the Rust programming language. Written by Willi Kappler, License: MIT -

95 Jan 1, 2023

Genetic Algorithm library in Rust

RsGenetic Summary and Features RsGenetic is a framework for executing genetic algorithms in Rust. It is designed to have a simple but modular API. Exa

74 Dec 27, 2022

Linear Programming for Rust, with an user-friendly API. This crate allows modeling LP problems, and let's you solve them with various solvers.

good_lp A Linear Programming modeler that is easy to use, performant with large problems, and well-typed. use good_lp::{variables, variable, coin_cbc,

101 Dec 27, 2022

Comments

Inner loop fix

This is essentially the most important fix as it directly addresses the bug and proposes a working (I hope) solution to it by rewriting the inner loop logic.

{
    let m = (l + r) / 2;
    if self[m] == i 
    {
        Some(m)
    }
    else 
    {
        if l != r
        {
            if self[m] > i
            {
                self.remove(m);
                // a special care is only needed for the left edge 
                // since "r" always is always bigger than "m" at least by 1
                if m == l { self.stalin(i, l, m) } 
                else { self.stalin(i, l, m - 1) }
            } 
            else 
            {
                self.remove(m);
                self.stalin(i, m, r - 1)
            }
        }
        else { None }
    }
}

opened by yanefingon 6

Better tests

The last one focuses on the addition of a more robust and unpredictable test (as those used in an original work were not capable of detecting the bug which is a shame).

opened by yanefingon 1
Tofixornottofix

Algorithm complexity theoretical analysis

This one aims at improving the theoretical basis of the project by providing the complexity analysis for the average running case as well as its upper and lower bound.
It fixes the corresponding info on the front page, as well.

hacktoberfest-accepted

opened by yanefingon 0