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!

7 Comments

  1. Posted July 2, 2018 at 6:11 pm | Permalink

    This could be a fantastic buy if you are looking to mend a
    toy hauler you already own. Many students of astral projection complain of dropping off to sleep while they perform the regular relaxation, meditation, and focusing
    required of them. Europeans may prefer Cuba, while Americans who can’t check out Cuba may seek comfort and familiarity in Puerto Rico as well as the US Virgin Islands.

  2. Posted January 9, 2021 at 8:43 pm | Permalink

    reproduced by hand, in contrast

  3. Posted January 9, 2021 at 9:04 pm | Permalink

    By the end of the 15th century, 35

  4. Posted January 19, 2021 at 1:35 am | Permalink

    then only a few have reached us

  5. Posted January 23, 2021 at 8:40 am | Permalink

    elements (case, binding).

  6. Posted February 26, 2021 at 11:43 am | Permalink

    By the end of the 15th century, 35

  7. Posted April 12, 2021 at 4:42 am | Permalink

    Western Europe also formed

Post a Comment

Your email is never shared. Required fields are marked *

*
*