Generic binary search in Rust

I’ve been using Rust lately, and I really love it.  I wrote a little binary search algorithm that’s generic over the container type, the index type, and the element type, and I thought I’d share it.

use std::cmp::Ordering;
use std::ops::Add;
use std::ops::Div;
use std::ops::Index;
use std::ops::Sub;

pub trait BinarySearch<I, T> {
  /// Returns the index of an equal key, or the index at which the key would be inserted if one does not exist.
  fn binary_search(&self, key: &T, mut lower: I, mut upper: I) -> I;
}

// // Would use this, but std::num::One is unstable
// impl <C, I, T> BinarySearch<I, T> for C
//   where
//    C: Index<I, Output = T>,
//     I: Ord + Add<Output = I> + Sub<Output = I> + Div<Output = I> + Shr<I, Output = I> + One + Copy,
//     T: Ord {
//   fn binary_search(&self, key: &T, mut lower: I, mut upper: I) -> I {
//     let one = I::one();
//     loop {
//       if upper <= lower {
//         return lower;
//       }
//       let mid = (lower + upper).shr(one);
//       match key.cmp(&self[mid]) {
//         Ordering::Less => upper = mid,
//         Ordering::Greater => lower = mid + one,
//         Ordering::Equal => return mid,
//       }
//     }
//   }
// }

impl <C, I, T> BinarySearch<I, T> for C
  where
   C: Index<I, Output = T>,
    I: Ord + Add<Output = I> + Sub<Output = I> + Div<Output = I> + Shr<I, Output = I> + Copy,
    T: Ord {
  fn binary_search(&self, key: &T, mut lower: I, mut upper: I) -> I {
    if upper == lower {
      return lower;
    }
    let one = (upper - lower) / (upper - lower);
    loop {
      if upper <= lower {
        return lower;
      }
      let mid = (lower + upper).shr(one);
      match key.cmp(&self[mid]) {
        Ordering::Less => upper = mid,
        Ordering::Greater => lower = mid + one,
        Ordering::Equal => return mid,
      }
    }
  }
}

#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn test_binary_search() {
    let data = vec![0, 0, 1, 2, 4, 7];
    for i in 0..data.len() {
      let ix = data.binary_search(&data[i], 0, data.len());
      assert_eq!(data[ix], data[i]); // ix may not be i because of duplicates
    }
    assert_eq!(data.binary_search(&-1, 0, data.len()), 0);
    assert_eq!(data.binary_search(&3, 0, data.len()), 4);
    assert_eq!(data.binary_search(&5, 0, data.len()), 5);
    assert_eq!(data.binary_search(&8, 0, data.len()), 6);
  }
}

Enjoy!

29 Trackbacks

  1. By chanel coco handle bag on January 18, 2022 at 1:27 am

    chanel coco handle bag

    Generic binary search in Rust – Blog

  2. By electriq tv remote app on January 18, 2022 at 2:11 pm

    electriq tv remote app

    Generic binary search in Rust – Blog

  3. By loratap tapparelle on January 18, 2022 at 3:05 pm

    loratap tapparelle

    Generic binary search in Rust – Blog

  4. By who makes electriq tvs on January 18, 2022 at 3:29 pm

    who makes electriq tvs

    Generic binary search in Rust – Blog

  5. By used tobacco pipes on January 18, 2022 at 3:30 pm

    used tobacco pipes

    Generic binary search in Rust – Blog

  6. By my webpage on January 18, 2022 at 3:35 pm

    my webpage

    Generic binary search in Rust – Blog

  7. By blue betsey johnson purse on January 18, 2022 at 4:08 pm

    blue betsey johnson purse

    Generic binary search in Rust – Blog

  8. By leather wallet for women on January 18, 2022 at 4:30 pm

    leather wallet for women

    Generic binary search in Rust – Blog

  9. By small black leather wallet womens on January 19, 2022 at 3:37 am

    small black leather wallet womens

    Generic binary search in Rust – Blog

  10. By small leather wallet on January 19, 2022 at 3:46 am

    small leather wallet

    Generic binary search in Rust – Blog

  11. By husqvarna chainsaw parts on January 19, 2022 at 11:42 pm

    husqvarna chainsaw parts

    Generic binary search in Rust – Blog

  12. By phanxy how to use on January 20, 2022 at 9:43 am

    phanxy how to use

    Generic binary search in Rust – Blog

  13. By Women's Clothing Boutiques on January 20, 2022 at 10:10 am

    Women’s Clothing Boutiques

    Generic binary search in Rust – Blog

  14. By celine handbags on January 20, 2022 at 10:24 am

    celine handbags

    Generic binary search in Rust – Blog

  15. click here to visit L.Iv.Eli.Ne.S.Swxzu@Hu.Feng.Ku.Angn.I.Ub.I.xn%26mdash;.xn%26mdash;.U.K37@cgi.members.interq.or.jp for free

    Generic binary search in Rust – Blog

  16. By women's clothing subscription box on January 20, 2022 at 11:10 am

    women’s clothing subscription box

    Generic binary search in Rust – Blog

  17. By Betsey Johnson Zip Around Wallet on January 20, 2022 at 11:51 am

    Betsey Johnson Zip Around Wallet

    Generic binary search in Rust – Blog

  18. By betsey johnson clutch wallet on January 20, 2022 at 1:16 pm

    betsey johnson clutch wallet

    Generic binary search in Rust – Blog

  19. By betsey johnson wallet macys on January 20, 2022 at 8:05 pm

    betsey johnson wallet macys

    Generic binary search in Rust – Blog

  20. By computer drawing Tablets on January 21, 2022 at 9:51 am

    computer drawing Tablets

    Generic binary search in Rust – Blog

  21. By best tobacco pipes for beginners on January 22, 2022 at 2:23 am

    best tobacco pipes for beginners

    Generic binary search in Rust – Blog

  22. By lowes digital caliper on January 23, 2022 at 3:26 am

    lowes digital caliper

    Generic binary search in Rust – Blog

  23. By computer tablets review on January 23, 2022 at 5:14 pm

    computer tablets review

    Generic binary search in Rust – Blog

  24. By hatsan air rifles reviews on January 25, 2022 at 7:17 am

    hatsan air rifles reviews

    Generic binary search in Rust – Blog

  25. By asian sexy movies on January 25, 2022 at 9:29 am

    asian sexy movies

    Generic binary search in Rust – Blog

  26. By exercise dvd for beginners on January 26, 2022 at 1:35 am

    exercise dvd for beginners

    Generic binary search in Rust – Blog

  27. By Going in Musiceagles on January 26, 2022 at 6:29 pm

    Going in Musiceagles

    Generic binary search in Rust – Blog

  28. By electronic digital caliper on January 26, 2022 at 6:49 pm

    electronic digital caliper

    Generic binary search in Rust – Blog

  29. By fossil crossbody bags on January 28, 2022 at 5:58 am

    fossil crossbody bags

    Generic binary search in Rust – Blog

Post a Comment

Your email is never shared. Required fields are marked *

*
*