Stalin Binary Search, Rust implementation

Overview

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.

#[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],
    );
  }
}
Issues
  • Overcrossing pointers vulnerability

    Overcrossing pointers vulnerability

    This one adds an overview of a pointer-overcrossing bug and brings an in-depth explanation of the problem as well as its roots. image

    hacktoberfest-accepted 
    opened by yanefingon 9
  • Inner loop fix

    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

    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

    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.

    image

    hacktoberfest-accepted 
    opened by yanefingon 0
  • Implementation for other collections

    Implementation for other collections

    https://doc.rust-lang.org/std/collections/index.html

    hacktoberfest 
    opened by Miezhiko 0
  • Write documentation for docs.rs

    Write documentation for docs.rs

    null

    hacktoberfest 
    opened by Miezhiko 0
Releases(0.0.4)
Owner
Иногда у меня смеются глаза, а пластыри обёрнутые вокруг моей кожи покрыты лезвиями. Я всегда хотела быть драконом, а не принцессой, запертой в замке.
null
Rust implementation of real-coded GA for solving optimization problems and training of neural networks

revonet Rust implementation of real-coded genetic algorithm for solving optimization problems and training of neural networks. The latter is also know

Yury Tsoy 17 Jun 28, 2021
Raft implementation in Rust

rsraft Raft implementation in Rust. The aim of this project is implementing the Raft Consensus Algorithm as described in the paper, with the goal of f

Lauro Caetano 38 May 5, 2021
Rust implementation of AstroBWT Proof-Of-Work algorithm

AstroBWT AstroBWT is a proof-of-work (PoW) algorithm based on Burrows-Wheeler transform (BWT). Developed and used by the DERO Project for Mobile (arm)

null 5 Sep 7, 2021
A SIMD-accelerated Adler-32 rolling hash algorithm implementation.

simd-adler32 A SIMD-accelerated Adler-32 rolling hash algorithm implementation. Features No dependencies Support no_std (with default-features = false

Marvin Countryman 19 Nov 20, 2021
An implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke collection of weighted hexagons.

An implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke collection of weighted hexagons. It's intended to calculate the most optimal path to a target hexagon where you are traversing from the centre of one hexagon to the next along a line orthogonal to a hexagon edge

null 15 Oct 21, 2021
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

Martín Pozo 122 Sep 24, 2021
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 -

Willi Kappler 78 Nov 14, 2021
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

Mathieu De Coster 66 Jul 2, 2021
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,

Rust Operations Research 58 Nov 15, 2021
A tool used to evaluate the output of retrieval algorithms. Written in Rust.

Rusteval A tool used to evaluate the output of retrieval algorithms. Written in Rust. Building Install Rust with curl -sSf https://static.rust-lang.or

Giorgos Sfikas 18 Jul 16, 2021
This crate implements fast route planning algorithms in Rust.

This crate implements fast route planning algorithms in Rust. Algorithms Currently implemented: Contraction Hierarchies: The implementat

Payas Rajan 4 Aug 15, 2021
A browser app that evolves vehicles using genetic algorithms, written in Rust and Bevy

Vehicle Evolver Deluxe This is a simulation that uses AI (to be specific: genetic algorithms) to try to build better and better vehicles. The vehicles

null 93 Nov 20, 2021
Supervised discretization in Rust

Discrust Supervised discretization in Rust The discrust package provides a supervised discretization algorithm. Under the hood it implements a decisio

James Inlow 1 Nov 27, 2021
"Algorithms for approximate string matching" in Rust, with Python bindings.

ukkonen Implementation of a bounded Levenshtein distance by Esko Ukkonen in "Algorithms for approximate string matching" in Rust, with Python bindings

Ethan Smith 1 Nov 19, 2021
cargo search, built for caching binary artifacts, optimized for GitHub Actions

cargo-search2 A binary utility that provides a more convenient version of cargo search. Installation Grab pre-built binaries for your platform from th

Rain 2 Oct 12, 2021
Binary coverage tool without binary modification for Windows

Summary Mesos is a tool to gather binary code coverage on all user-land Windows targets without need for source or recompilation. It also provides an

null 352 Nov 19, 2021
Rust binary memcached implementation

bmemcached-rs Rust binary memcached implementation (ON GOING) Usage extern crate bmemcached; use std::sync::Arc; use std::thread; use bmemcached::Me

Jayson Reis 22 Mar 15, 2021
A binary encoder / decoder implementation in Rust.

Bincode A compact encoder / decoder pair that uses a binary zero-fluff encoding scheme. The size of the encoded object will be the same or smaller tha

Bincode 1.3k Nov 28, 2021
🦀 The ultimate search extension for Rust

Rust Search Extension 简体中文 The ultimate search extension for Rust Search docs, crates, builtin attributes, official books, and error codes, etc in you

Huhu 681 Nov 30, 2021
Ternary search tree collection in rust

tst Ternary search tree collection in rust with similar API to std::collections as it possible. Ternary search tree is a type of trie (sometimes calle

Alexey Pervushin 17 Sep 12, 2021
Rust edit distance routines accelerated using SIMD. Supports fast Hamming, Levenshtein, restricted Damerau-Levenshtein, etc. distance calculations and string search.

triple_accel Rust edit distance routines accelerated using SIMD. Supports fast Hamming, Levenshtein, restricted Damerau-Levenshtein, etc. distance cal

Daniel Liu 50 Nov 21, 2021
Tantivy is a full-text search engine library inspired by Apache Lucene and written in Rust

Tantivy is a full text search engine library written in Rust. It is closer to Apache Lucene than to Elasticsearch or Apache Solr in the sense it is no

tantivy 5.6k Nov 30, 2021
A full-text search and indexing server written in Rust.

Bayard Bayard is a full-text search and indexing server written in Rust built on top of Tantivy that implements Raft Consensus Algorithm and gRPC. Ach

Bayard Search 1.5k Nov 23, 2021
AI-powered search engine for Rust

txtai: AI-powered search engine for Rust txtai executes machine-learning workflows to transform data and build AI-powered text indices to perform simi

NeuML 56 Nov 23, 2021
A full-text search engine in rust

Toshi A Full-Text Search Engine in Rust Please note that this is far from production ready, also Toshi is still under active development, I'm just slo

Toshi Search 3.3k Nov 25, 2021
🚀 efficient approximate nearest neighbor search algorithm collections library written in Rust 🦀 .

?? efficient approximate nearest neighbor search algorithm collections library written in Rust ?? .

Hora-Search 2.1k Nov 26, 2021
🔭 Search Dash.app from Neovim with Telescope. Built with Rust 🦀 and Lua

Dash.nvim Query Dash.app within Neovim with a Telescope picker! The theme used in the recording is lighthaus.nvim. Note: Dash is a Mac-only app, so yo

Mat Jones 94 Nov 30, 2021
A Rust API search engine

Roogle Roogle is a Rust API search engine, which allows you to search functions by names and type signatures. Progress Available Queries Function quer

Roogle 222 Nov 17, 2021
rga: ripgrep, but also search in PDFs, E-Books, Office documents, zip, tar.gz, etc.

rga: ripgrep, but also search in PDFs, E-Books, Office documents, zip, tar.gz, etc. rga is a line-oriented search tool that allows you to look for a r

null 4.2k Nov 24, 2021