1044 Intermediate

1044-sorted-vec — Sorted Vec with Binary Search

Functional Programming

Tutorial

The Problem

When you need sorted iteration AND fast membership tests but do not need to insert and delete frequently, a sorted Vec<T> is more cache-efficient than a BTreeSet. Binary search over a contiguous array benefits from hardware prefetching, while pointer-heavy B-tree nodes fragment the cache. The sorted_vec and bsearch crates exploit this trade-off.

partition_point (Rust 1.52) and binary_search provide O(log n) insertion point and lookup over a sorted Vec.

🎯 Learning Outcomes

• Maintain a sorted Vec<T> using partition_point for O(log n) insert position

• Use binary_search for O(log n) membership test

• Compare sorted Vec to BTreeSet for read-heavy vs write-heavy workloads

• Use partition_point for bisection (lower bound equivalent)

• Implement range queries on sorted Vec using partition_point on both ends

Code Example

#![allow(clippy::all)]
// 1044: Sorted Vec — Binary Search Insert with partition_point
// Maintain a sorted Vec with O(log n) search and O(n) insert

/// A sorted vector that maintains order on insertion
struct SortedVec<T: Ord> {
    data: Vec<T>,
}

impl<T: Ord> SortedVec<T> {
    fn new() -> Self {
        SortedVec { data: Vec::new() }
    }

    /// Insert maintaining sorted order — O(log n) search + O(n) shift
    fn insert(&mut self, value: T) {
        let pos = self.data.partition_point(|x| x < &value);
        self.data.insert(pos, value);
    }

    /// Binary search — O(log n)
    fn contains(&self, value: &T) -> bool {
        self.data.binary_search(value).is_ok()
    }

    /// Find index of value — O(log n)
    fn find(&self, value: &T) -> Option<usize> {
        self.data.binary_search(value).ok()
    }

    /// Remove a value — O(log n) search + O(n) shift
    fn remove(&mut self, value: &T) -> bool {
        if let Ok(pos) = self.data.binary_search(value) {
            self.data.remove(pos);
            true
        } else {
            false
        }
    }

    fn len(&self) -> usize {
        self.data.len()
    }

    fn as_slice(&self) -> &[T] {
        &self.data
    }

    /// Range query: elements in [lo, hi]
    fn range(&self, lo: &T, hi: &T) -> &[T] {
        let start = self.data.partition_point(|x| x < lo);
        let end = self.data.partition_point(|x| x <= hi);
        &self.data[start..end]
    }
}

fn basic_sorted_vec() {
    let mut sv = SortedVec::new();
    sv.insert(5);
    sv.insert(3);
    sv.insert(7);
    sv.insert(1);
    sv.insert(4);

    assert_eq!(sv.as_slice(), &[1, 3, 4, 5, 7]);
    assert!(sv.contains(&4));
    assert!(!sv.contains(&6));
    assert_eq!(sv.find(&5), Some(3));
}

fn partition_point_demo() {
    let data = vec![1, 3, 5, 7, 9, 11];

    // partition_point: first index where predicate is false
    let pos = data.partition_point(|&x| x < 6);
    assert_eq!(pos, 3); // Insert point for 6

    let pos = data.partition_point(|&x| x < 5);
    assert_eq!(pos, 2); // 5 would go at index 2

    // binary_search returns Ok(index) or Err(insert_point)
    assert_eq!(data.binary_search(&5), Ok(2));
    assert_eq!(data.binary_search(&6), Err(3));
}

fn range_query() {
    let mut sv = SortedVec::new();
    for x in [1, 3, 5, 7, 9, 11] {
        sv.insert(x);
    }

    assert_eq!(sv.range(&3, &9), &[3, 5, 7, 9]);
    assert_eq!(sv.range(&4, &8), &[5, 7]);
    assert_eq!(sv.range(&20, &30), &[] as &[i32]);
}

fn remove_test() {
    let mut sv = SortedVec::new();
    for x in [1, 2, 3, 4, 5] {
        sv.insert(x);
    }

    assert!(sv.remove(&3));
    assert_eq!(sv.as_slice(), &[1, 2, 4, 5]);
    assert!(!sv.remove(&3)); // Already removed
}

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

    #[test]
    fn test_basic() {
        basic_sorted_vec();
    }

    #[test]
    fn test_partition_point() {
        partition_point_demo();
    }

    #[test]
    fn test_range() {
        range_query();
    }

    #[test]
    fn test_remove() {
        remove_test();
    }

    #[test]
    fn test_duplicates() {
        let mut sv = SortedVec::new();
        sv.insert(1);
        sv.insert(1);
        sv.insert(2);
        assert_eq!(sv.as_slice(), &[1, 1, 2]);
    }
}

(* 1044: Sorted Vec — Binary Search Insert *)
(* Maintain a sorted list/array with efficient search *)

(* Approach 1: Sorted list with binary search on array *)
let binary_search arr target =
  let rec go lo hi =
    if lo >= hi then lo
    else
      let mid = lo + (hi - lo) / 2 in
      if arr.(mid) < target then go (mid + 1) hi
      else go lo mid
  in
  go 0 (Array.length arr)

let sorted_array_ops () =
  let arr = [|1; 3; 5; 7; 9; 11|] in
  assert (binary_search arr 5 = 2);
  assert (binary_search arr 6 = 3);  (* insertion point *)
  assert (binary_search arr 0 = 0);
  assert (binary_search arr 12 = 6)

(* Approach 2: Sorted list with insertion *)
let sorted_insert lst x =
  let rec go = function
    | [] -> [x]
    | (h :: _) as l when x <= h -> x :: l
    | h :: t -> h :: go t
  in
  go lst

let sorted_list_ops () =
  let lst = [] in
  let lst = sorted_insert lst 5 in
  let lst = sorted_insert lst 3 in
  let lst = sorted_insert lst 7 in
  let lst = sorted_insert lst 1 in
  let lst = sorted_insert lst 4 in
  assert (lst = [1; 3; 4; 5; 7])

(* Approach 3: Sorted collection operations *)
let sorted_contains lst x =
  (* Linear for list, but maintains concept *)
  List.exists (fun e -> e = x) lst

let sorted_merge a b =
  let rec go a b =
    match a, b with
    | [], r | r, [] -> r
    | x :: xs, y :: ys ->
      if x <= y then x :: go xs (y :: ys)
      else y :: go (x :: xs) ys
  in
  go a b

let sorted_dedup lst =
  let rec go = function
    | [] | [_] as l -> l
    | x :: (y :: _ as rest) ->
      if x = y then go rest
      else x :: go rest
  in
  go lst

let collection_ops () =
  let a = [1; 3; 5; 7] in
  let b = [2; 3; 6; 8] in
  let merged = sorted_merge a b in
  assert (merged = [1; 2; 3; 3; 5; 6; 7; 8]);
  let deduped = sorted_dedup merged in
  assert (deduped = [1; 2; 3; 5; 6; 7; 8])

let () =
  sorted_array_ops ();
  sorted_list_ops ();
  collection_ops ();
  Printf.printf "✓ All tests passed\n"

Key Differences

**partition_point**: Rust's partition_point is the canonical lower-bound bisection; OCaml's Base.Array.binary_search with ~how: parameter provides equivalent.

Insert cost: Both languages have O(n) insert due to element shifting; BTreeSet / Set.Make are O(log n) insert.

Cache efficiency: Both benefit from contiguous memory access during binary search; sorted arrays beat tree structures for read-heavy workloads.

Range iteration: Rust's slice indexing after partition_point is zero-copy; OCaml's Array.sub allocates a new array.

OCaml Approach

OCaml's arrays with Array.blit for insertion and binary search:

let binary_search arr target =
  let lo = ref 0 and hi = ref (Array.length arr - 1) in
  let result = ref None in
  while !lo <= !hi do
    let mid = (!lo + !hi) / 2 in
    if arr.(mid) = target then (result := Some mid; lo := !hi + 1)
    else if arr.(mid) < target then lo := mid + 1
    else hi := mid - 1
  done;
  !result

The Base.Array.binary_search function provides a one-liner. Sorted arrays are the standard for static lookup tables in OCaml.

Full Source

#![allow(clippy::all)]
// 1044: Sorted Vec — Binary Search Insert with partition_point
// Maintain a sorted Vec with O(log n) search and O(n) insert

/// A sorted vector that maintains order on insertion
struct SortedVec<T: Ord> {
    data: Vec<T>,
}

impl<T: Ord> SortedVec<T> {
    fn new() -> Self {
        SortedVec { data: Vec::new() }
    }

    /// Insert maintaining sorted order — O(log n) search + O(n) shift
    fn insert(&mut self, value: T) {
        let pos = self.data.partition_point(|x| x < &value);
        self.data.insert(pos, value);
    }

    /// Binary search — O(log n)
    fn contains(&self, value: &T) -> bool {
        self.data.binary_search(value).is_ok()
    }

    /// Find index of value — O(log n)
    fn find(&self, value: &T) -> Option<usize> {
        self.data.binary_search(value).ok()
    }

    /// Remove a value — O(log n) search + O(n) shift
    fn remove(&mut self, value: &T) -> bool {
        if let Ok(pos) = self.data.binary_search(value) {
            self.data.remove(pos);
            true
        } else {
            false
        }
    }

    fn len(&self) -> usize {
        self.data.len()
    }

    fn as_slice(&self) -> &[T] {
        &self.data
    }

    /// Range query: elements in [lo, hi]
    fn range(&self, lo: &T, hi: &T) -> &[T] {
        let start = self.data.partition_point(|x| x < lo);
        let end = self.data.partition_point(|x| x <= hi);
        &self.data[start..end]
    }
}

fn basic_sorted_vec() {
    let mut sv = SortedVec::new();
    sv.insert(5);
    sv.insert(3);
    sv.insert(7);
    sv.insert(1);
    sv.insert(4);

    assert_eq!(sv.as_slice(), &[1, 3, 4, 5, 7]);
    assert!(sv.contains(&4));
    assert!(!sv.contains(&6));
    assert_eq!(sv.find(&5), Some(3));
}

fn partition_point_demo() {
    let data = vec![1, 3, 5, 7, 9, 11];

    // partition_point: first index where predicate is false
    let pos = data.partition_point(|&x| x < 6);
    assert_eq!(pos, 3); // Insert point for 6

    let pos = data.partition_point(|&x| x < 5);
    assert_eq!(pos, 2); // 5 would go at index 2

    // binary_search returns Ok(index) or Err(insert_point)
    assert_eq!(data.binary_search(&5), Ok(2));
    assert_eq!(data.binary_search(&6), Err(3));
}

fn range_query() {
    let mut sv = SortedVec::new();
    for x in [1, 3, 5, 7, 9, 11] {
        sv.insert(x);
    }

    assert_eq!(sv.range(&3, &9), &[3, 5, 7, 9]);
    assert_eq!(sv.range(&4, &8), &[5, 7]);
    assert_eq!(sv.range(&20, &30), &[] as &[i32]);
}

fn remove_test() {
    let mut sv = SortedVec::new();
    for x in [1, 2, 3, 4, 5] {
        sv.insert(x);
    }

    assert!(sv.remove(&3));
    assert_eq!(sv.as_slice(), &[1, 2, 4, 5]);
    assert!(!sv.remove(&3)); // Already removed
}

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

    #[test]
    fn test_basic() {
        basic_sorted_vec();
    }

    #[test]
    fn test_partition_point() {
        partition_point_demo();
    }

    #[test]
    fn test_range() {
        range_query();
    }

    #[test]
    fn test_remove() {
        remove_test();
    }

    #[test]
    fn test_duplicates() {
        let mut sv = SortedVec::new();
        sv.insert(1);
        sv.insert(1);
        sv.insert(2);
        assert_eq!(sv.as_slice(), &[1, 1, 2]);
    }
}

(* 1044: Sorted Vec — Binary Search Insert *)
(* Maintain a sorted list/array with efficient search *)

(* Approach 1: Sorted list with binary search on array *)
let binary_search arr target =
  let rec go lo hi =
    if lo >= hi then lo
    else
      let mid = lo + (hi - lo) / 2 in
      if arr.(mid) < target then go (mid + 1) hi
      else go lo mid
  in
  go 0 (Array.length arr)

let sorted_array_ops () =
  let arr = [|1; 3; 5; 7; 9; 11|] in
  assert (binary_search arr 5 = 2);
  assert (binary_search arr 6 = 3);  (* insertion point *)
  assert (binary_search arr 0 = 0);
  assert (binary_search arr 12 = 6)

(* Approach 2: Sorted list with insertion *)
let sorted_insert lst x =
  let rec go = function
    | [] -> [x]
    | (h :: _) as l when x <= h -> x :: l
    | h :: t -> h :: go t
  in
  go lst

let sorted_list_ops () =
  let lst = [] in
  let lst = sorted_insert lst 5 in
  let lst = sorted_insert lst 3 in
  let lst = sorted_insert lst 7 in
  let lst = sorted_insert lst 1 in
  let lst = sorted_insert lst 4 in
  assert (lst = [1; 3; 4; 5; 7])

(* Approach 3: Sorted collection operations *)
let sorted_contains lst x =
  (* Linear for list, but maintains concept *)
  List.exists (fun e -> e = x) lst

let sorted_merge a b =
  let rec go a b =
    match a, b with
    | [], r | r, [] -> r
    | x :: xs, y :: ys ->
      if x <= y then x :: go xs (y :: ys)
      else y :: go (x :: xs) ys
  in
  go a b

let sorted_dedup lst =
  let rec go = function
    | [] | [_] as l -> l
    | x :: (y :: _ as rest) ->
      if x = y then go rest
      else x :: go rest
  in
  go lst

let collection_ops () =
  let a = [1; 3; 5; 7] in
  let b = [2; 3; 6; 8] in
  let merged = sorted_merge a b in
  assert (merged = [1; 2; 3; 3; 5; 6; 7; 8]);
  let deduped = sorted_dedup merged in
  assert (deduped = [1; 2; 3; 5; 6; 7; 8])

let () =
  sorted_array_ops ();
  sorted_list_ops ();
  collection_ops ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_basic() {
        basic_sorted_vec();
    }

    #[test]
    fn test_partition_point() {
        partition_point_demo();
    }

    #[test]
    fn test_range() {
        range_query();
    }

    #[test]
    fn test_remove() {
        remove_test();
    }

    #[test]
    fn test_duplicates() {
        let mut sv = SortedVec::new();
        sv.insert(1);
        sv.insert(1);
        sv.insert(2);
        assert_eq!(sv.as_slice(), &[1, 1, 2]);
    }
}

Deep Comparison

Sorted Vec — Comparison

Core Insight

A sorted vector trades O(n) insertion for O(log n) search and excellent cache locality. For small to medium collections, it often outperforms tree-based structures. Rust provides binary_search, partition_point, and slice-based range queries; OCaml uses manual binary search on arrays or sorted list insertion.

OCaml Approach

• Sorted list: sorted_insert walks list to find position — O(n)

• Array binary search: manual implementation with lo/hi

• Merge of sorted lists: classic merge algorithm

• Deduplication on sorted data: skip consecutive equals

• No built-in binary_search on arrays

Rust Approach

• Vec::binary_search(): returns Ok(idx) or Err(insert_point)

• partition_point(|x| x < &val): first index where predicate fails

• Vec::insert(pos, val): shifts elements right — O(n)

• Slice-based range queries via partition_point for both bounds

• binary_search for exact match, partition_point for bounds

Comparison Table

Feature	OCaml	Rust
Binary search	Manual	`binary_search()` / `partition_point()`
Insert	List walk O(n)	`insert(pos, val)` O(n)
Search result	Index	`Result<usize, usize>`
Range query	Manual slice	`partition_point` × 2
Cache locality	List: poor / Array: good	Vec: excellent
Dedup	Manual walk	`dedup()` built-in

Exercises

Add remove(&mut self, value: &T) -> bool using binary_search to find the index and Vec::remove to remove it.

Write count_in_range(lo: &T, hi: &T) -> usize using two partition_point calls and subtraction.

Implement merge_sorted(a: SortedVec<T>, b: SortedVec<T>) -> SortedVec<T> in O(n) using the merge step from merge sort.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust