Binary Search and Sorted Data Structures

Problem Statement

Build efficient search and query systems leveraging binary search on sorted data. Implement various binary search variants (exact match, lower bound, upper bound, range queries) and create data structures that maintain sorted invariants for O(log n) operations.

Your project should include:

• Generic binary search implementation (exact, lower_bound, upper_bound)
• Database-like range queries on sorted data
• Auto-complete / prefix matching with binary search
• Efficient merging of sorted sequences (k-way merge)
• Maintaining sorted invariants for incremental updates
• Performance comparisons with linear search and hash-based approaches

Example use case:

Sorted log entries by timestamp (1M entries)
Query: Find all logs between 10:00 and 10:05
Linear scan: O(n) = 1M comparisons
Binary search range: O(log n + k) = 20 comparisons + k results
Speedup: 50,000x for k=1000 results

Why It Matters

Binary search is one of the most fundamental algorithms: O(log n) vs O(n) is the difference between 20 operations and 1,000,000 operations for n=1M. Many production systems rely on sorted data: databases (B-trees), file systems, network routing tables, autocomplete systems.

Key Concepts Explained

1. Binary Search Algorithm (Divide and Conquer)

Binary search finds an element in a sorted array by repeatedly halving the search space.

Precondition: Array must be sorted!

Algorithm:

#![allow(unused)]
fn main() {
fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;  // Avoid overflow

        match arr[mid].cmp(&target) {
            Ordering::Equal => return Some(mid),     // Found!
            Ordering::Less => left = mid + 1,        // Search right half
            Ordering::Greater => right = mid,        // Search left half
        }
    }
    None  // Not found
}
}

Visual example: Search for 7 in [1, 3, 5, 7, 9, 11, 13]

Step 1: left=0, right=7
        mid = 3 → arr[3] = 7 → FOUND!

If searching for 6:
Step 1: left=0, right=7, mid=3 → arr[3]=7 > 6 → search left
Step 2: left=0, right=3, mid=1 → arr[1]=3 < 6 → search right
Step 3: left=2, right=3, mid=2 → arr[2]=5 < 6 → search right
Step 4: left=3, right=3 → NOT FOUND (left >= right)

Why O(log n)?

• Each step halves search space: n → n/2 → n/4 → n/8 → … → 1
• Steps needed: log₂(n)
• For n=1,000,000: log₂(1,000,000) ≈ 20 steps

Comparison to linear search:

2. Lower Bound and Upper Bound (Range Boundaries)

Lower bound: First position where arr[i] >= target (leftmost insertion point) Upper bound: First position where arr[i] > target (rightmost insertion point)

Why they matter: Enable range queries without scanning.

Lower bound algorithm:

#![allow(unused)]
fn main() {
fn lower_bound(arr: &[i32], target: i32) -> usize {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if arr[mid] < target {
            left = mid + 1;  // Too small, go right
        } else {
            right = mid;      // Could be answer or too large
        }
    }
    left  // First position >= target
}
}

Upper bound algorithm:

#![allow(unused)]
fn main() {
fn upper_bound(arr: &[i32], target: i32) -> usize {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if arr[mid] <= target {  // Note: <= not <
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    left  // First position > target
}
}

Visual example: Array [1, 3, 3, 3, 5, 7, 9], target = 3

lower_bound(3) = 1  (first 3 at index 1)
upper_bound(3) = 4  (first element > 3 is 5 at index 4)

Range [lower, upper) = [1, 4) gives all 3's: [3, 3, 3]

Use cases:

• Range queries: Find all elements in [5, 11]
• Insertion point: Where to insert to maintain sorted order
• Count occurrences: upper_bound(x) - lower_bound(x)

3. Range Queries on Sorted Data

Range query: Find all elements in range [start, end] using two binary searches.

Algorithm:

#![allow(unused)]
fn main() {
fn range_query<T: Ord>(arr: &[T], start: &T, end: &T) -> &[T] {
    let lower = lower_bound(arr, start);  // First element >= start
    let upper = upper_bound(arr, end);     // First element > end
    &arr[lower..upper]  // Slice containing range
}
}

Visual example: Find range [5, 11] in [1, 3, 5, 7, 9, 11, 13, 15]

Array:  [1, 3, 5, 7, 9, 11, 13, 15]
Index:   0  1  2  3  4   5   6   7

lower_bound(5)  = 2  (index of 5)
upper_bound(11) = 6  (index after 11)

Result: arr[2..6] = [5, 7, 9, 11]

Complexity: O(log n + k) where k is result size

• O(log n): Two binary searches
• O(k): Return k results

Comparison to linear scan:

4. Prefix Matching (Binary Search on Strings)

Prefix matching: Find all strings starting with given prefix in sorted array.

Algorithm:

#![allow(unused)]
fn main() {
fn prefix_search<'a>(words: &'a [String], prefix: &str) -> &'a [String] {
    // Find first word >= prefix
    let start = words.partition_point(|w| w.as_str() < prefix);

    // Scan forward while words start with prefix
    let mut end = start;
    while end < words.len() && words[end].starts_with(prefix) {
        end += 1;
    }

    &words[start..end]
}
}

Visual example: Find prefix “app” in sorted words

Words: ["apple", "application", "apply", "banana", "band"]
         ^^^^^    ^^^^^^^^^^^    ^^^^^
         match    match          match

Step 1: Binary search finds start = 0 (first word >= "app")
Step 2: Scan: "apple".starts_with("app") ✓
             "application".starts_with("app") ✓
             "apply".starts_with("app") ✓
             "banana".starts_with("app") ✗ → STOP
Result: &words[0..3] = ["apple", "application", "apply"]

Optimization trick (upper bound):

#![allow(unused)]
fn main() {
// Instead of scanning, use upper bound with next prefix
fn prefix_range(words: &[String], prefix: &str) -> &[String] {
    let start = lower_bound(words, prefix);

    // Compute next prefix: "app" → "apq" (increment last char)
    let next_prefix = next_prefix(prefix);
    let end = lower_bound(words, &next_prefix);

    &words[start..end]
}

fn next_prefix(s: &str) -> String {
    let mut bytes = s.bytes().collect::<Vec<_>>();
    if let Some(last) = bytes.last_mut() {
        *last += 1;
    }
    String::from_utf8(bytes).unwrap()
}
}

Complexity: O(log n + k) where k is matches

• Binary search: O(log n)
• Scanning: O(k) or none with trick

5. K-Way Merge with Min-Heap

K-way merge: Merge k sorted sequences into one sorted sequence efficiently.

Naive approach (repeated 2-way merge): O(nk)

#![allow(unused)]
fn main() {
// Merge 100 sequences sequentially
let mut result = seq[0].clone();
for i in 1..100 {
    result = merge_two(&result, &seq[i]);  // Expensive!
}
// Each merge processes all previous elements
}

Heap approach: O(n log k)

#![allow(unused)]
fn main() {
// Min-heap tracks smallest element from each sequence
let mut heap = BinaryHeap::new();

// Initialize: Add first element from each sequence
for (seq_idx, seq) in sequences.iter().enumerate() {
    if let Some(&first) = seq.first() {
        heap.push(Reverse((first, seq_idx, 0)));
    }
}

// Extract min, push next from same sequence
while let Some(Reverse((value, seq_idx, elem_idx))) = heap.pop() {
    result.push(value);

    let next_idx = elem_idx + 1;
    if next_idx < sequences[seq_idx].len() {
        heap.push(Reverse((sequences[seq_idx][next_idx], seq_idx, next_idx)));
    }
}
}

Visual example: Merge 3 sequences

Seq 0: [1, 4, 7]
Seq 1: [2, 5, 8]
Seq 2: [3, 6, 9]

Heap initially: [(1, seq=0, idx=0), (2, seq=1, idx=0), (3, seq=2, idx=0)]

Step 1: Pop (1, 0, 0) → output 1, push (4, 0, 1)
        Heap: [(2, 1, 0), (3, 2, 0), (4, 0, 1)]

Step 2: Pop (2, 1, 0) → output 2, push (5, 1, 1)
        Heap: [(3, 2, 0), (4, 0, 1), (5, 1, 1)]

Step 3: Pop (3, 2, 0) → output 3, push (6, 2, 1)
...
Result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Complexity comparison (n total elements, k sequences):

6. SortedVec vs BTreeSet vs HashSet

Three collection types with different tradeoffs:

SortedVec: Vector maintaining sorted order

#![allow(unused)]
fn main() {
struct SortedVec<T> { data: Vec<T> }

// Insert: O(n) - binary search O(log n) + shift O(n)
// Search: O(log n) - binary search
// Range: O(log n + k) - binary search bounds
}

BTreeSet: B-tree (balanced tree)

#![allow(unused)]
fn main() {
use std::collections::BTreeSet;

// Insert: O(log n) - tree insertion
// Search: O(log n) - tree traversal
// Range: O(log n + k) - tree range
}

HashSet: Hash table

#![allow(unused)]
fn main() {
use std::collections::HashSet;

// Insert: O(1) - hash + insert
// Search: O(1) - hash lookup
// Range: ✗ - no ordering
}

Performance comparison:

When to use each:

• SortedVec: Small sets (<1K), read-heavy, need ranges, cache-sensitive
• BTreeSet: Large sets (>1K), need ordering, balanced read/write
• HashSet: No ordering needed, membership test only, write-heavy

7. Cache Locality and Memory Layout

Cache locality: Accessing nearby memory is much faster than random access.

Modern CPU cache hierarchy:

L1 cache:  32-64KB,  ~4 cycles   (fastest)
L2 cache:  256KB,    ~12 cycles
L3 cache:  8-32MB,   ~40 cycles
RAM:       16GB,     ~200 cycles (slowest)

SortedVec (cache-friendly):

Memory layout: [1][3][5][7][9][11][13][15]
               ↑ Contiguous array in memory

Binary search: Sequential memory accesses within nearby region
Cache prefetcher: Loads next cache line automatically
Result: ~4-12 cycles per access (L1/L2 hits)

BTreeSet (cache-unfriendly):

Memory layout:
Node 1 → [7, 15] → Node 2 → [3, 5] → Node 3 → [1]
         |         |                  |
       (ptr)     (ptr)              (ptr)

Tree traversal: Random pointer chasing
Cache misses: Each node in different cache line
Result: ~40-200 cycles per access (L3/RAM)

Measured impact (1000 elements, 1M searches):

SortedVec:  L1/L2 cache hits ~95%,  10ms
BTreeSet:   L3/RAM access ~60%,     50ms (5× slower!)

Why SortedVec can beat BTreeSet for small n:

• O(n) with great cache locality beats O(log n) with poor locality
• Crossover point: ~1000-2000 elements

8. Partition Point (Generalized Binary Search)

partition_point: Find boundary where predicate changes from false to true.

Signature:

#![allow(unused)]
fn main() {
fn partition_point<P>(arr: &[T], pred: P) -> usize
where
    P: FnMut(&T) -> bool
}

Concept: Array is partitioned into [false*, true*], find first true.

Example: Find first element >= 5 in [1, 3, 5, 7, 9]

#![allow(unused)]
fn main() {
let pos = arr.partition_point(|&x| x < 5);
// Predicate: x < 5
// Values:    [T, T, F, F, F]
//                  ↑ First false at index 2
// Result: 2 (index of 5)
}

Why it’s powerful: Generalizes binary search to any monotonic predicate.

Use cases:

#![allow(unused)]
fn main() {
// Lower bound (first element >= target)
let lower = arr.partition_point(|x| x < &target);

// Upper bound (first element > target)
let upper = arr.partition_point(|x| x <= &target);

// First element satisfying predicate
let pos = arr.partition_point(|x| !predicate(x));

// Custom: First element where f(x) > threshold
let pos = arr.partition_point(|x| compute(x) <= threshold);
}

9. Binary Search Invariants (Loop Correctness)

Binary search correctness depends on maintaining invariants.

Key invariant:

If element exists, it's in range [left, right)

Proof by induction:

Initial: left=0, right=n
  If element exists, it's in [0, n) ✓ (entire array)

Loop iteration:
  mid = (left + right) / 2

  If arr[mid] < target:
    Element must be in (mid, right)
    Set left = mid + 1
    Invariant preserved: [mid+1, right)

  If arr[mid] > target:
    Element must be in [left, mid)
    Set right = mid
    Invariant preserved: [left, mid)

  If arr[mid] == target:
    Found! Return mid

Termination: left == right
  If element existed, it would be at position left
  If arr[left] != target, element doesn't exist

Common bug (off-by-one):

#![allow(unused)]
fn main() {
// WRONG: Infinite loop possible
while left < right {
    mid = (left + right) / 2;
    if arr[mid] < target {
        left = mid;  // BUG: If mid == left, infinite loop!
    } else {
        right = mid - 1;  // BUG: Might skip answer!
    }
}

// CORRECT:
while left < right {
    mid = (left + right) / 2;
    if arr[mid] < target {
        left = mid + 1;  // Always progresses
    } else {
        right = mid;  // Preserves invariant
    }
}
}

10. Overflow-Safe Midpoint Calculation

Naive midpoint can overflow:

#![allow(unused)]
fn main() {
let mid = (left + right) / 2;  // OVERFLOW if left + right > MAX
}

Problem:

left = 1,000,000,000
right = 2,000,000,000
left + right = 3,000,000,000  // Overflow on 32-bit int! (max = 2^31 - 1 ≈ 2.1B)

Safe alternatives:

Method 1: Subtraction

#![allow(unused)]
fn main() {
let mid = left + (right - left) / 2;

// Proof: right >= left (invariant)
// right - left <= n (array size)
// left + (right - left) / 2 <= left + n / 2 <= n (no overflow)
}

Method 2: Unsigned average

#![allow(unused)]
fn main() {
let mid = (left + right) >> 1;  // Bit shift right (divide by 2)
// Works if using unsigned integers
}

Method 3: Average with carry

#![allow(unused)]
fn main() {
let mid = left + (right - left) / 2;
// Or equivalently:
let mid = (left & right) + ((left ^ right) >> 1);
}

Why it matters: Production code must handle edge cases.

Connection to This Project

This project demonstrates how binary search and sorted data structures enable logarithmic-time operations across diverse use cases.

Milestone 1: Implement Binary Search Variants

Concepts applied:

• Binary search algorithm (divide and conquer)
• Lower bound and upper bound
• Invariants and loop correctness
• Overflow-safe midpoint calculation
• Generic programming (T: Ord)

Why it matters: Binary search is the foundation of all sorted data operations:

• O(log n) vs O(n): For n=1M, that’s 20 ops vs 1M ops (50,000× speedup)
• Lower/upper bounds enable range queries
• Variants handle duplicates correctly

Real-world impact:

#![allow(unused)]
fn main() {
// Linear search (O(n))
fn linear_search(arr: &[i32], target: i32) -> Option<usize> {
    arr.iter().position(|&x| x == target)
    // 1,000,000 comparisons for n=1M
}

// Binary search (O(log n))
fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    // Uses divide-and-conquer
    // 20 comparisons for n=1M (50,000× faster!)
}
}

Performance comparison (1M elements):

Real-world validation:

• Databases: All index lookups use binary search on B-trees
• File systems: Directory lookups (sorted inodes)
• Git: Commit lookup by hash (sorted pack files)

Milestone 2: Range Queries with Binary Search

Concepts applied:

• Range queries using lower/upper bounds
• Zero-copy slicing
• Complexity O(log n + k) where k is result size
• Custom Ord implementation for domain types

Why it matters: Range queries are essential for time-series, logs, and filtering:

• Two binary searches find range boundaries in O(log n)
• Return slice (zero-copy) containing results
• Vastly faster than linear scan for sparse results

Real-world impact:

#![allow(unused)]
fn main() {
// Linear scan (O(n))
let results: Vec<&LogEntry> = logs.iter()
    .filter(|log| log.timestamp >= start && log.timestamp <= end)
    .collect();
// Scans all 1M logs: 1M comparisons

// Binary range query (O(log n + k))
let range = range_query(&logs, &start_log, &end_log);
// Two binary searches: 40 comparisons + k results
}

Performance comparison (1M logs, find 100 in range):

Real-world use cases:

• Log analysis: “Show errors between 10:00 and 10:05”
• Time-series DB: Query sensor data by timestamp range
• Event sourcing: Replay events in time window

Milestone 3: Auto-Complete with Prefix Matching

Concepts applied:

• Prefix matching on sorted strings
• partition_point for generalized binary search
• Scanning vs upper bound trick
• Sort + dedup for preprocessing

Why it matters: Auto-complete is ubiquitous (search bars, IDEs, shells):

• Binary search finds prefix start in O(log n)
• Scan or upper bound trick finds end
• Simple and fast for moderate dictionaries (10K-1M words)

Real-world impact:

#![allow(unused)]
fn main() {
// Linear scan (check every word)
let matches: Vec<&str> = words.iter()
    .filter(|w| w.starts_with(prefix))
    .collect();
// Scans 100K words: 100K prefix checks

// Binary prefix search
let matches = prefix_search(&words, prefix);
// Binary search: log(100K) ≈ 17 comparisons
// Scan matches: k prefix checks
// For k=10: ~27 operations (3,700× faster!)
}

Performance comparison (100K words, 10 matches):

Real-world examples:

• VS Code: File/symbol autocomplete (100K+ symbols)
• Shell: Command completion (sorted PATH commands)
• Browser: URL autocomplete (history + bookmarks)

Alternative (Trie): Trie is O(m) where m is prefix length, but:

• O(n) space overhead (pointers)
• More complex implementation
• SortedVec+binary search wins for <1M words

Milestone 4: Merge Sorted Sequences (K-Way Merge)

Concepts applied:

• K-way merge with min-heap
• Heap priority queue (BinaryHeap)
• Complexity O(n log k) vs O(nk)
• Reverse wrapper for min-heap

Why it matters: Merging sorted sequences is fundamental to:

• External merge sort (disk-based sorting)
• Log aggregation (multiple sources)
• Database query optimization (merge join)

Real-world impact:

#![allow(unused)]
fn main() {
// Naive: Repeated 2-way merge (O(nk))
let mut result = seq[0].clone();
for seq in &seqs[1..] {
    result = merge_two(&result, seq);  // Each merge costs O(n)
}
// For k=100 seqs, n=1M each:  100M operations

// K-way heap merge (O(n log k))
let result = merge_k(&seqs);
// For k=100 seqs, n=1M each: 6.6M operations (15× faster!)
}

Performance comparison (100 sequences, 10K elements each):

Real-world applications:

• External sort: Merge sort for data > RAM (disk-based)
• Log aggregation: Merge logs from 100 servers by timestamp
• Database merge join: Merge sorted tables efficiently

Milestone 5: Sorted Set with Incremental Updates

Concepts applied:

• SortedVec maintaining sorted invariant
• Binary search for insertion point
• O(n) insert/remove (shifting)
• When SortedVec beats BTreeSet (cache locality)

Why it matters: Dynamic sorted collections with updates:

• SortedVec: O(n) inserts but excellent cache locality
• BTreeSet: O(log n) inserts but pointer chasing
• For n<1000, SortedVec can be faster due to caching

Real-world impact:

#![allow(unused)]
fn main() {
// Insert 1000 elements
let mut sv = SortedVec::new();
for i in 0..1000 {
    sv.insert(i);  // O(n) binary search + shift
}
// Time: ~5ms (great cache locality)

let mut btree = BTreeSet::new();
for i in 0..1000 {
    btree.insert(i);  // O(log n) tree insertion
}
// Time: ~8ms (pointer chasing, cache misses)
}

Performance comparison (1000 elements, 1M searches):

When to use SortedVec:

• ✅ Small collections (<1K elements)
• ✅ Read-heavy (90% search, 10% write)
• ✅ Need range queries
• ❌ Large collections (>1K, BTreeSet wins)
• ❌ Write-heavy (HashSet or BTreeSet better)

Milestone 6: Performance Optimization and Trade-offs

Concepts applied:

• Benchmarking methodology
• Cache locality impact
• Asymptotic complexity vs constant factors
• Decision framework for collection choice

Why it matters: Choosing the right data structure is critical:

• Big-O notation doesn’t tell the full story
• Cache locality can dominate for small n
• Production systems need informed decisions

Real-world impact:

#![allow(unused)]
fn main() {
// Benchmark results (real hardware):

Size 100:
  SortedVec: 0.5ms (cache-friendly)
  BTreeSet:  1.2ms (pointer overhead)
  HashSet:   0.3ms (fastest, no ordering)

Size 1,000:
  SortedVec: 8ms   (still competitive)
  BTreeSet:  6ms   (starting to win)
  HashSet:   2ms   (still fastest)

Size 10,000:
  SortedVec: 150ms (O(n²) hurts)
  BTreeSet:  40ms  (O(log n) wins)
  HashSet:   15ms  (O(1) wins)

Size 100,000:
  SortedVec: 15,000ms (unusable)
  BTreeSet:  500ms     (best for ordering)
  HashSet:   150ms     (best overall)
}

Decision framework:

Production lessons:

1. Measure, don’t guess: Benchmark your specific workload
2. Cache matters: O(n) can beat O(log n) for small n
3. Consider all operations: Don’t optimize just insert or just search
4. Know crossover points: ~1000 elements for SortedVec vs BTreeSet

Milestone 1: Implement Binary Search Variants

Goal: Implement exact match, lower_bound, upper_bound binary searches.

What to implement:

• binary_search_exact(): Find exact match, return index
• binary_search_lower_bound(): Find first element >= target
• binary_search_upper_bound(): Find first element > target
• Generic implementations that work with any ordered type

Starter Code:

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

/// Binary search for exact match
/// Role: O(log n) exact search
pub fn binary_search_exact<T: Ord>(arr: &[T], target: &T) -> Option<usize> {
    todo!("Implement binary search with left/right pointers")
}

/// Binary search for lower bound
/// Role: Range query start point
pub fn binary_search_lower_bound<T: Ord>(arr: &[T], target: &T) -> usize {
    todo!("Find leftmost position where arr[i] >= target")
}

/// Binary search for upper bound
/// Role: Range query end point
pub fn binary_search_upper_bound<T: Ord>(arr: &[T], target: &T) -> usize {
    todo!("Find leftmost position where arr[i] > target")
}

/// Helper: Check if array is sorted
/// Role: Validate precondition
pub fn is_sorted<T: Ord>(arr: &[T]) -> bool {
    todo!("Check arr[i] <= arr[i+1] for all i")
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_exact_search_found() {
        let arr = vec![1, 3, 5, 7, 9, 11, 13];

        assert_eq!(binary_search_exact(&arr, &5), Some(2));
        assert_eq!(binary_search_exact(&arr, &1), Some(0));
        assert_eq!(binary_search_exact(&arr, &13), Some(6));
    }

    #[test]
    fn test_exact_search_not_found() {
        let arr = vec![1, 3, 5, 7, 9];

        assert_eq!(binary_search_exact(&arr, &2), None);
        assert_eq!(binary_search_exact(&arr, &0), None);
        assert_eq!(binary_search_exact(&arr, &10), None);
    }

    #[test]
    fn test_exact_search_empty() {
        let arr: Vec<i32> = vec![];
        assert_eq!(binary_search_exact(&arr, &5), None);
    }

    #[test]
    fn test_exact_search_duplicates() {
        let arr = vec![1, 3, 3, 3, 5, 7];

        // Should find one of the 3's (any is valid)
        let result = binary_search_exact(&arr, &3);
        assert!(result.is_some());
        assert_eq!(arr[result.unwrap()], 3);
    }

    #[test]
    fn test_lower_bound() {
        let arr = vec![1, 3, 5, 7, 9];

        assert_eq!(binary_search_lower_bound(&arr, &5), 2); // Exact match
        assert_eq!(binary_search_lower_bound(&arr, &4), 2); // Between 3 and 5
        assert_eq!(binary_search_lower_bound(&arr, &0), 0); // Before all
        assert_eq!(binary_search_lower_bound(&arr, &10), 5); // After all
    }

    #[test]
    fn test_lower_bound_duplicates() {
        let arr = vec![1, 3, 3, 3, 5, 7];

        // Should return first 3
        assert_eq!(binary_search_lower_bound(&arr, &3), 1);
    }

    #[test]
    fn test_upper_bound() {
        let arr = vec![1, 3, 5, 7, 9];

        assert_eq!(binary_search_upper_bound(&arr, &5), 3); // After 5
        assert_eq!(binary_search_upper_bound(&arr, &4), 2); // Between 3 and 5
        assert_eq!(binary_search_upper_bound(&arr, &0), 0); // Before all
        assert_eq!(binary_search_upper_bound(&arr, &9), 5); // After all
    }

    #[test]
    fn test_upper_bound_duplicates() {
        let arr = vec![1, 3, 3, 3, 5, 7];

        // Should return index after last 3
        assert_eq!(binary_search_upper_bound(&arr, &3), 4);
    }

    #[test]
    fn test_bounds_with_strings() {
        let arr = vec!["apple", "banana", "cherry", "date"];

        assert_eq!(binary_search_lower_bound(&arr, &"banana"), 1);
        assert_eq!(binary_search_upper_bound(&arr, &"banana"), 2);
    }

    #[test]
    fn test_is_sorted() {
        assert!(is_sorted(&[1, 2, 3, 4, 5]));
        assert!(is_sorted(&[1, 1, 2, 3])); // Duplicates OK
        assert!(!is_sorted(&[1, 3, 2, 4]));
        assert!(is_sorted(&Vec::<i32>::new())); // Empty is sorted
    }
}
}

Milestone 2: Range Queries with Binary Search

Goal: Implement efficient range queries: find all elements in [start, end].

Why the previous milestone is not enough: Single element lookup is useful, but range queries are essential for time-series, databases, and filtering operations.

What’s the improvement: Range queries using two binary searches are O(log n + k) where k is result size. Naive linear scan is O(n). For finding 100 elements in 1M element array:

• Linear scan: ~1,000,000 comparisons
• Binary search range: ~40 comparisons + 100 results

This is a 10,000x speedup for the search phase.

Optimization focus: Speed through binary search (O(n) → O(log n + k)).

Architecture:

• Functions:
  • range_query<T: Ord>(arr: &[T], start: &T, end: &T) -> &[T] - Get slice in range
  • count_in_range<T: Ord>(arr: &[T], start: &T, end: &T) -> usize - Count without materializing
  • Example types: LogEntry with timestamp ordering

For LogEntry with custom ordering:

• Implement Ord based on timestamp
• Create dummy entries with target timestamps for comparison
• Use range_query on the sorted log array

Starter Code:

#![allow(unused)]
fn main() {
/// Range query on sorted array
/// Role: Zero-copy range extraction
pub fn range_query<T: Ord>(arr: &[T], start: &T, end: &T) -> &[T] {
    todo!("Use lower_bound(start) and upper_bound(end)")
}

/// Count elements in range
/// Role: Efficient counting
pub fn count_in_range<T: Ord>(arr: &[T], start: &T, end: &T) -> usize {
    todo!("Return upper_bound(end) - lower_bound(start)")
}

/// Log entry with timestamp
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LogEntry {
    pub timestamp: u64,             // Unix timestamp                 
    pub level: String,              // Log level (INFO, ERROR, etc.)   
    pub message: String,            // Log message                   
}

impl Ord for LogEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        self.timestamp.cmp(&other.timestamp)
    }
}

impl PartialOrd for LogEntry {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// Query logs by time range
/// Role: Time-series query
pub fn query_logs_by_time(logs: &[LogEntry], start_time: u64, end_time: u64) -> &[LogEntry] {
    todo!("Create dummy entries for bounds, use range_query")
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_range_query_basic() {
        let arr = vec![1, 3, 5, 7, 9, 11, 13, 15];

        let result = range_query(&arr, &5, &11);
        assert_eq!(result, &[5, 7, 9, 11]);
    }

    #[test]
    fn test_range_query_empty() {
        let arr = vec![1, 3, 5, 7, 9];

        let result = range_query(&arr, &20, &30);
        assert_eq!(result.len(), 0);
    }

    #[test]
    fn test_range_query_all() {
        let arr = vec![1, 3, 5, 7, 9];

        let result = range_query(&arr, &0, &10);
        assert_eq!(result, &arr[..]);
    }

    #[test]
    fn test_count_in_range() {
        let arr = vec![1, 3, 5, 7, 9, 11, 13, 15];

        assert_eq!(count_in_range(&arr, &5, &11), 4); // 5, 7, 9, 11
        assert_eq!(count_in_range(&arr, &0, &20), 8); // All
        assert_eq!(count_in_range(&arr, &20, &30), 0); // None
    }

    #[test]
    fn test_range_query_duplicates() {
        let arr = vec![1, 3, 3, 3, 5, 7, 7, 9];

        let result = range_query(&arr, &3, &7);
        assert_eq!(result, &[3, 3, 3, 5, 7, 7]);
    }

    #[test]
    fn test_log_entry_ordering() {
        let log1 = LogEntry {
            timestamp: 100,
            level: "INFO".to_string(),
            message: "Message 1".to_string(),
        };

        let log2 = LogEntry {
            timestamp: 200,
            level: "ERROR".to_string(),
            message: "Message 2".to_string(),
        };

        assert!(log1 < log2);
    }

    #[test]
    fn test_query_logs_by_time() {
        let logs = vec![
            LogEntry { timestamp: 100, level: "INFO".to_string(), message: "Msg 1".to_string() },
            LogEntry { timestamp: 200, level: "INFO".to_string(), message: "Msg 2".to_string() },
            LogEntry { timestamp: 300, level: "ERROR".to_string(), message: "Msg 3".to_string() },
            LogEntry { timestamp: 400, level: "INFO".to_string(), message: "Msg 4".to_string() },
        ];

        let result = query_logs_by_time(&logs, 200, 300);

        assert_eq!(result.len(), 2);
        assert_eq!(result[0].timestamp, 200);
        assert_eq!(result[1].timestamp, 300);
    }

    #[test]
    fn test_range_performance_vs_linear() {
        use std::time::Instant;

        let arr: Vec<i32> = (0..1_000_000).collect();

        // Binary search range query
        let start = Instant::now();
        let result1 = range_query(&arr, &100_000, &100_100);
        let binary_time = start.elapsed();

        // Linear scan
        let start = Instant::now();
        let result2: Vec<&i32> = arr.iter()
            .filter(|&&x| x >= 100_000 && x <= 100_100)
            .collect();
        let linear_time = start.elapsed();

        assert_eq!(result1.len(), result2.len());

        println!("Binary search: {:?}", binary_time);
        println!("Linear scan: {:?}", linear_time);

        // Binary search should be dramatically faster
        assert!(binary_time < linear_time);
    }
}
}

Milestone 3: Auto-Complete with Prefix Matching

Goal: Implement auto-complete using binary search on sorted strings.

Why the previous milestone is not enough: Exact and range queries work for known values, but prefix matching is needed for search, auto-complete, and fuzzy finding.

What’s the improvement: Binary search + prefix scan is O(log n + k) where k is matches. Building a trie would be O(n) space and complex. For moderate-sized dictionaries (10K-1M words), sorted array + binary search is simpler and faster.

Optimization focus: Simplicity and speed for moderate datasets.

Architecture:

• Structs: AutoComplete
• Functions:
  • prefix_search<'a>(words: &'a [String], prefix: &str) -> &'a [String] - Find prefix matches
  • AutoComplete::new(words: Vec<String>) -> Self - Create with sorted words
  • AutoComplete::suggest(&self, prefix: &str) -> Vec<&str> - Get suggestions

Starter Code:

#![allow(unused)]
fn main() {
/// Find all strings with given prefix
/// Role: Efficient prefix matching
pub fn prefix_search<'a>(words: &'a [String], prefix: &str) -> &'a [String] {
    todo!("Use partition_point to find start, scan while prefix matches")
}

/// Auto-complete system
/// Role: Fast prefix suggestions
#[derive(Debug)]
pub struct AutoComplete {
    words: Vec<String>,                 // Sorted, deduplicated words 
}

impl AutoComplete {
    /// Create auto-complete with word list
    /// Role: Initialize and sort
    pub fn new(mut words: Vec<String>) -> Self {
        todo!("Sort and deduplicate words")
    }

    /// Get suggestions for prefix
    /// Role: Return top N matches
    pub fn suggest(&self, prefix: &str) -> Vec<&str> {
        todo!("Use prefix_search, take top 10")
    }

    /// Get all matches (no limit)
    /// Role: Complete result set
    pub fn suggest_all(&self, prefix: &str) -> Vec<&str> {
        todo!("Return all prefix matches")
    }

    /// Get word count
    /// Role: Query dictionary size
    pub fn word_count(&self) -> usize {
        self.words.len()
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_prefix_search_basic() {
        let words = vec![
            "apple".to_string(),
            "application".to_string(),
            "apply".to_string(),
            "banana".to_string(),
            "band".to_string(),
        ];

        let result = prefix_search(&words, "app");
        assert_eq!(result.len(), 3);
        assert!(result.contains(&"apple".to_string()));
        assert!(result.contains(&"application".to_string()));
        assert!(result.contains(&"apply".to_string()));
    }

    #[test]
    fn test_prefix_search_empty_prefix() {
        let words = vec!["apple".to_string(), "banana".to_string()];

        let result = prefix_search(&words, "");
        assert_eq!(result.len(), 2); // All words
    }

    #[test]
    fn test_prefix_search_no_matches() {
        let words = vec!["apple".to_string(), "banana".to_string()];

        let result = prefix_search(&words, "xyz");
        assert_eq!(result.len(), 0);
    }

    #[test]
    fn test_autocomplete_creation() {
        let words = vec![
            "banana".to_string(),
            "apple".to_string(),
            "apple".to_string(), // Duplicate
            "cherry".to_string(),
        ];

        let ac = AutoComplete::new(words);

        // Should be sorted and deduplicated
        assert_eq!(ac.word_count(), 3);
    }

    #[test]
    fn test_autocomplete_suggestions() {
        let words = vec![
            "apple".to_string(),
            "application".to_string(),
            "apply".to_string(),
            "appreciate".to_string(),
            "banana".to_string(),
        ];

        let ac = AutoComplete::new(words);
        let suggestions = ac.suggest("app");

        assert!(suggestions.len() > 0);
        assert!(suggestions.len() <= 10); // Limited to 10
    }

    #[test]
    fn test_autocomplete_suggest_all() {
        let words = vec![
            "test1".to_string(),
            "test2".to_string(),
            "test3".to_string(),
            "other".to_string(),
        ];

        let ac = AutoComplete::new(words);
        let all_suggestions = ac.suggest_all("test");

        assert_eq!(all_suggestions.len(), 3);
    }

    #[test]
    fn test_autocomplete_case_sensitive() {
        let words = vec![
            "Apple".to_string(),
            "apple".to_string(),
            "APPLE".to_string(),
        ];

        let ac = AutoComplete::new(words);

        // Should treat as different words
        assert_eq!(ac.word_count(), 3);
    }

    #[test]
    fn test_autocomplete_performance() {
        use std::time::Instant;

        // Create large dictionary
        let words: Vec<String> = (0..100_000)
            .map(|i| format!("word{:06}", i))
            .collect();

        let ac = AutoComplete::new(words);

        // Benchmark suggestions
        let start = Instant::now();

        for _ in 0..1000 {
            let _ = ac.suggest("word1");
        }

        let elapsed = start.elapsed();

        println!("Time for 1000 lookups: {:?}", elapsed);

        // Should be very fast
        assert!(elapsed.as_millis() < 100);
    }

    #[test]
    fn test_autocomplete_real_world() {
        let words = vec![
            "javascript".to_string(),
            "java".to_string(),
            "python".to_string(),
            "rust".to_string(),
            "ruby".to_string(),
            "go".to_string(),
        ];

        let ac = AutoComplete::new(words);

        assert_eq!(ac.suggest("ja").len(), 2); // java, javascript
        assert_eq!(ac.suggest("r").len(), 2);  // ruby, rust
        assert_eq!(ac.suggest("xyz").len(), 0); // No matches
    }
}
}

Milestone 4: Merge Sorted Sequences (K-Way Merge)

Goal: Efficiently merge multiple sorted sequences.

Why the previous milestone is not enough: Individual sorted sequences are useful, but often we need to combine multiple sources (log files, database shards, sorted chunks).

What’s the improvement: K-way merge with heap is O(n log k) where n is total elements, k is number of sequences. Repeated 2-way merge is O(nk). For k=100:

• Repeated 2-way: 100× slower
• K-way with heap: Optimal

Optimization focus: Speed through better algorithm.

Architecture:

• Functions:
  • merge_two<T: Ord + Clone>(left: &[T], right: &[T]) -> Vec<T> - Two-way merge
  • merge_k<T: Ord + Clone>(sequences: &[&[T]]) -> Vec<T> - K-way merge with heap

Starter Code:

#![allow(unused)]
fn main() {
use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// Merge two sorted slices
/// Role: Building block for merge sort
pub fn merge_two<T: Ord + Clone>(left: &[T], right: &[T]) -> Vec<T> {
    todo!("Two-pointer merge algorithm")
}

/// Merge K sorted sequences using heap
/// Role: Combine multiple sorted sources
pub fn merge_k<T: Ord + Clone>(sequences: &[&[T]]) -> Vec<T> {
    todo!("Use BinaryHeap with (value, seq_index, elem_index)")
}

/// Merge iterator (lazy evaluation)
/// Role: Zero-allocation merging
pub struct MergeIterator<'a, T> {
    sequences: Vec<&'a [T]>,
    indices: Vec<usize>,
    heap: BinaryHeap<Reverse<(T, usize)>>,
}

impl<'a, T: Ord + Clone> MergeIterator<'a, T> {
    /// Create merge iterator
    /// Role: Initialize heap with first elements
    pub fn new(sequences: Vec<&'a [T]>) -> Self {
        todo!("Initialize heap, indices")
    }
}

impl<'a, T: Ord + Clone> Iterator for MergeIterator<'a, T> {
    type Item = T;

    /// Get next merged element
    /// Role: Lazy merging
    fn next(&mut self) -> Option<Self::Item> {
        todo!("Pop from heap, push next from same sequence")
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_merge_two_basic() {
        let left = vec![1, 3, 5];
        let right = vec![2, 4, 6];

        let result = merge_two(&left, &right);

        assert_eq!(result, vec![1, 2, 3, 4, 5, 6]);
    }

    #[test]
    fn test_merge_two_empty() {
        let left = vec![1, 2, 3];
        let right: Vec<i32> = vec![];

        let result = merge_two(&left, &right);
        assert_eq!(result, vec![1, 2, 3]);
    }

    #[test]
    fn test_merge_two_overlapping() {
        let left = vec![1, 5, 9];
        let right = vec![3, 7, 11];

        let result = merge_two(&left, &right);
        assert_eq!(result, vec![1, 3, 5, 7, 9, 11]);
    }

    #[test]
    fn test_merge_k_basic() {
        let seq1 = vec![1, 4, 7];
        let seq2 = vec![2, 5, 8];
        let seq3 = vec![3, 6, 9];

        let sequences = vec![&seq1[..], &seq2[..], &seq3[..]];
        let result = merge_k(&sequences);

        assert_eq!(result, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    }

    #[test]
    fn test_merge_k_different_lengths() {
        let seq1 = vec![1, 2];
        let seq2 = vec![3, 4, 5, 6];
        let seq3 = vec![7];

        let sequences = vec![&seq1[..], &seq2[..], &seq3[..]];
        let result = merge_k(&sequences);

        assert_eq!(result, vec![1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_merge_k_with_duplicates() {
        let seq1 = vec![1, 3, 5];
        let seq2 = vec![1, 3, 5];

        let sequences = vec![&seq1[..], &seq2[..]];
        let result = merge_k(&sequences);

        assert_eq!(result, vec![1, 1, 3, 3, 5, 5]);
    }

    #[test]
    fn test_merge_k_single_sequence() {
        let seq1 = vec![1, 2, 3];

        let sequences = vec![&seq1[..]];
        let result = merge_k(&sequences);

        assert_eq!(result, vec![1, 2, 3]);
    }

    #[test]
    fn test_merge_k_empty_sequences() {
        let empty: Vec<i32> = vec![];
        let sequences: Vec<&[i32]> = vec![&empty];

        let result = merge_k(&sequences);
        assert_eq!(result.len(), 0);
    }

    #[test]
    fn test_merge_performance() {
        use std::time::Instant;

        // Create 10 sorted sequences of 10000 elements each
        let sequences: Vec<Vec<i32>> = (0..10)
            .map(|i| (i..100000).step_by(10).collect())
            .collect();

        let seq_refs: Vec<&[i32]> = sequences.iter().map(|v| v.as_slice()).collect();

        // K-way merge
        let start = Instant::now();
        let result_k = merge_k(&seq_refs);
        let k_way_time = start.elapsed();

        // Repeated 2-way merge
        let start = Instant::now();
        let mut result_2way = sequences[0].clone();
        for seq in &sequences[1..] {
            result_2way = merge_two(&result_2way, seq);
        }
        let two_way_time = start.elapsed();

        println!("K-way merge: {:?}", k_way_time);
        println!("Repeated 2-way: {:?}", two_way_time);

        assert_eq!(result_k.len(), result_2way.len());

        // K-way should be faster
        assert!(k_way_time < two_way_time);
    }

    #[test]
    fn test_merge_iterator() {
        let seq1 = vec![1, 4, 7];
        let seq2 = vec![2, 5, 8];
        let seq3 = vec![3, 6, 9];

        let sequences = vec![&seq1[..], &seq2[..], &seq3[..]];
        let iter = MergeIterator::new(sequences);

        let result: Vec<i32> = iter.collect();

        assert_eq!(result, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    }
}
}

Milestone 5: Sorted Set with Incremental Updates

Goal: Maintain sorted collection with efficient insert/remove/search.

Why the previous milestone is not enough: Static sorted arrays are fast for queries but can’t handle updates. Need dynamic sorted collection.

What’s the improvement: Binary search for insertion point gives O(log n) search + O(n) shift. Still faster than hash table for small sets (<1000 elements) due to cache locality. Provides range queries and ordering that hash tables don’t support.

Optimization focus: When to use SortedVec vs BTreeSet vs HashSet.

Architecture:

• Structs: SortedVec<T>
• Fields: data: Vec<T>
• Functions:
  • new() -> Self - Create empty set
  • insert(value: T) -> bool - Add maintaining order
  • remove(value: &T) -> bool - Remove if present
  • contains(value: &T) -> bool - O(log n) search
  • range(start: &T, end: &T) -> &[T] - Range query

Starter Code:

#![allow(unused)]
fn main() {
/// Sorted vector maintaining order invariant
/// Role: Efficient sorted set for small-medium collections
#[derive(Debug, Clone)]
pub struct SortedVec<T> {
    data: Vec<T>,                  // : Ordered set using Vec    
}

impl<T: Ord> SortedVec<T> {
    /// Create empty sorted vec
    /// Role: Initialize
    pub fn new() -> Self {
        todo!("Create empty Vec")
    }

    /// Insert value maintaining order
    /// Role: O(log n) search + O(n) insert
    pub fn insert(&mut self, value: T) -> bool {
        todo!("Binary search position, insert if not present")
    }

    /// Remove value if present
    /// Role: O(log n) search + O(n) remove
    pub fn remove(&mut self, value: &T) -> bool {
        todo!("Binary search, remove if found")
    }

    /// Check if contains value
    /// Role: O(log n) membership test
    pub fn contains(&self, value: &T) -> bool {
        todo!("Use binary_search")
    }

    /// Get range of values
    /// Role: Range query support
    pub fn range(&self, start: &T, end: &T) -> &[T] {
        todo!("Use range_query helper")
    }

    /// Get length
    /// Role: Query size
    pub fn len(&self) -> usize {
        todo!()
    }

    /// Check if empty
    /// Role: Query emptiness
    pub fn is_empty(&self) -> bool {
       todo!()
    }

    /// Get all elements as slice
    /// Role: Zero-copy access
    pub fn as_slice(&self) -> &[T] {
          todo!()
    }
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::{BTreeSet, HashSet};
    use std::time::Instant;

    #[test]
    fn test_sorted_vec_insert() {
        let mut sv = SortedVec::new();

        assert!(sv.insert(5));
        assert!(sv.insert(3));
        assert!(sv.insert(7));
        assert!(sv.insert(1));

        assert_eq!(sv.as_slice(), &[1, 3, 5, 7]);
    }

    #[test]
    fn test_sorted_vec_insert_duplicate() {
        let mut sv = SortedVec::new();

        assert!(sv.insert(5));
        assert!(!sv.insert(5)); // Duplicate

        assert_eq!(sv.len(), 1);
    }

    #[test]
    fn test_sorted_vec_remove() {
        let mut sv = SortedVec::new();

        sv.insert(1);
        sv.insert(3);
        sv.insert(5);

        assert!(sv.remove(&3));
        assert_eq!(sv.as_slice(), &[1, 5]);

        assert!(!sv.remove(&10)); // Not present
    }

    #[test]
    fn test_sorted_vec_contains() {
        let mut sv = SortedVec::new();

        sv.insert(1);
        sv.insert(3);
        sv.insert(5);

        assert!(sv.contains(&3));
        assert!(!sv.contains(&4));
    }

    #[test]
    fn test_sorted_vec_range() {
        let mut sv = SortedVec::new();

        for i in vec![1, 3, 5, 7, 9, 11, 13] {
            sv.insert(i);
        }

        let range = sv.range(&5, &11);
        assert_eq!(range, &[5, 7, 9, 11]);
    }

    #[test]
    fn test_sorted_vec_maintains_order() {
        let mut sv = SortedVec::new();

        // Insert in random order
        for i in vec![9, 3, 7, 1, 5] {
            sv.insert(i);
        }

        // Should be sorted
        assert_eq!(sv.as_slice(), &[1, 3, 5, 7, 9]);
    }

    #[test]
    fn test_benchmark_vs_btreeset() {
        let n = 1000;

        // SortedVec
        let mut sv = SortedVec::new();
        let start = Instant::now();
        for i in 0..n {
            sv.insert(i);
        }
        let sv_insert_time = start.elapsed();

        // BTreeSet
        let mut btree = BTreeSet::new();
        let start = Instant::now();
        for i in 0..n {
            btree.insert(i);
        }
        let btree_insert_time = start.elapsed();

        println!("SortedVec insert (n={}): {:?}", n, sv_insert_time);
        println!("BTreeSet insert (n={}): {:?}", n, btree_insert_time);

        // For small n, SortedVec might be competitive
        // For large n, BTreeSet should win
    }

    #[test]
    fn test_benchmark_vs_hashset() {
        let n = 1000;

        // SortedVec
        let mut sv = SortedVec::new();
        let start = Instant::now();
        for i in 0..n {
            sv.insert(i);
        }
        let sv_time = start.elapsed();

        // HashSet
        let mut hs = HashSet::new();
        let start = Instant::now();
        for i in 0..n {
            hs.insert(i);
        }
        let hs_time = start.elapsed();

        println!("SortedVec: {:?}", sv_time);
        println!("HashSet: {:?}", hs_time);

        // HashSet should be faster for insertion
        // But SortedVec provides ordering
    }

    #[test]
    fn test_sorted_vec_use_case() {
        // Use case: Maintain sorted list of active user IDs
        let mut active_users = SortedVec::new();

        active_users.insert(101);
        active_users.insert(105);
        active_users.insert(103);

        // Get users in range
        let users_100_to_104 = active_users.range(&100, &104);
        assert_eq!(users_100_to_104, &[101, 103]);

        // Remove user
        active_users.remove(&103);

        // Check membership
        assert!(!active_users.contains(&103));
        assert!(active_users.contains(&105));
    }
}
}

Milestone 6: Performance Optimization and Trade-offs

Goal: Understand when to use different data structures and optimize critical paths.

Why the previous milestone is not enough: Having implementations is good, but understanding trade-offs is essential for making the right choice in production.

What’s the improvement: This milestone focuses on measurement, comparison, and decision-making:

• SortedVec: Best for <1K elements, cache-friendly, supports ranges
• BTreeSet: Best for >1K elements, O(log n) all operations
• HashSet: Best for membership only, no ordering

Optimization focus: Making informed architectural decisions.

Starter Code:

#![allow(unused)]
fn main() {
/// Benchmark framework for collection comparisons
/// Role: Compare data structures
pub struct CollectionBenchmark {
    sizes: Vec<usize>,
}

impl CollectionBenchmark {
    /// Create benchmark suite
    /// Role: Initialize test sizes
    pub fn new(sizes: Vec<usize>) -> Self {
        todo!("Store sizes to test")
    }

    /// Benchmark insertions
    /// Role: Measure insert performance
    pub fn benchmark_inserts(&self) {
        todo!("Test SortedVec, BTreeSet, HashSet insertions")
    }

    /// Benchmark lookups
    /// Role: Measure search performance
    pub fn benchmark_lookups(&self) {
        todo!("Test contains() performance")
    }

    /// Benchmark range queries
    /// Role: Measure range performance
    pub fn benchmark_ranges(&self) {
        todo!("Test range queries (SortedVec vs BTreeSet)")
    }

    /// Memory usage comparison
    /// Role: Measure space efficiency
    pub fn measure_memory(&self) {
        todo!("Estimate memory overhead")
    }

    /// Generate report
    /// Role: Summary of findings
    pub fn generate_report(&self) {
        todo!("Print comparison table")
    }
}

/// Trade-off analysis
/// Role: Decision support
pub fn recommend_collection(
    size: usize,
    needs_ordering: bool,
    needs_ranges: bool,
    write_heavy: bool,
) -> &'static str {
    todo!("Return recommendation based on requirements")
}
}

Checkpoint Tests:

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_recommendation_small_ordered() {
        let rec = recommend_collection(100, true, true, false);
        assert_eq!(rec, "SortedVec");
    }

    #[test]
    fn test_recommendation_large_ordered() {
        let rec = recommend_collection(10000, true, false, false);
        assert_eq!(rec, "BTreeSet");
    }

    #[test]
    fn test_recommendation_unordered() {
        let rec = recommend_collection(10000, false, false, true);
        assert_eq!(rec, "HashSet");
    }

    #[test]
    fn test_benchmark_suite() {
        let benchmark = CollectionBenchmark::new(vec![100, 1000, 10000]);

        // Run benchmarks
        benchmark.benchmark_inserts();
        benchmark.benchmark_lookups();
        benchmark.benchmark_ranges();

        // Generate report
        benchmark.generate_report();
    }

    #[test]
    fn test_cache_locality() {
        use std::time::Instant;

        let n = 10000;

        // Sequential access (cache-friendly)
        let data: Vec<i32> = (0..n).collect();
        let start = Instant::now();
        let sum1: i32 = data.iter().sum();
        let sequential_time = start.elapsed();

        // Random access (cache-unfriendly simulation)
        let indices: Vec<usize> = (0..n).rev().collect();
        let start = Instant::now();
        let sum2: i32 = indices.iter().map(|&i| data[i]).sum();
        let random_time = start.elapsed();

        assert_eq!(sum1, sum2);

        println!("Sequential: {:?}", sequential_time);
        println!("Random: {:?}", random_time);

        // Sequential should be faster
        assert!(sequential_time < random_time);
    }
}
}

Implementations

Implementation Milestone 1:

#![allow(unused)]
fn main() {
// Exact match implementation:
pub fn binary_search_exact<T: Ord>(arr: &[T], target: &T) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;  // Avoid overflow

        match arr[mid].cmp(target) {
            Ordering::Equal => return Some(mid),
            Ordering::Less => left = mid + 1,
            Ordering::Greater => right = mid,
        }
    }
    None
}

// Lower bound (first element >= target):
pub fn binary_search_lower_bound<T: Ord>(arr: &[T], target: &T) -> usize {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if arr[mid] < target {
            left = mid + 1;  // Move right
        } else {
            right = mid;      // Could be answer, keep searching left
        }
    }
    left
}

// Upper bound (first element > target):
pub fn binary_search_upper_bound<T: Ord>(arr: &[T], target: &T) -> usize {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if arr[mid] <= target {  // Note: <= not <
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    left
}
}

Implementation Milestone 2

#![allow(unused)]
fn main() {
pub fn range_query<T: Ord>(arr: &[T], start: &T, end: &T) -> &[T] {
    let lower = binary_search_lower_bound(arr, start);
    let upper = binary_search_upper_bound(arr, end);
    &arr[lower..upper]
}
}

Implementation Milestone 3:

#![allow(unused)]
fn main() {
pub fn prefix_search<'a>(words: &'a [String], prefix: &str) -> &'a [String] {
    // Find start position using partition_point
    let start = words.partition_point(|word| word.as_str() < prefix);

    // Find end by counting matches
    let mut end = start;
    while end < words.len() && words[end].starts_with(prefix) {
        end += 1;
    }

    &words[start..end]
}
}

Implementation Milestone 3:

#![allow(unused)]
fn main() {
impl AutoComplete {
    pub fn new(mut words: Vec<String>) -> Self {
        words.sort_unstable();      // Sort words
        words.dedup();              // Remove duplicates
        Self { words }
    }

    pub fn suggest(&self, prefix: &str) -> Vec<&str> {
        prefix_search(&self.words, prefix)
            .iter()
            .take(10)               // Limit to 10 suggestions
            .map(|s| s.as_str())
            .collect()
    }
}
}

Implementation Milestone 4:

#![allow(unused)]
fn main() {
use std::collections::BinaryHeap;
use std::cmp::Reverse;

pub fn merge_k<T: Ord + Clone>(sequences: &[&[T]]) -> Vec<T> {
    let total_size: usize = sequences.iter().map(|s| s.len()).sum();
    let mut result = Vec::with_capacity(total_size);

    // Heap stores: (value, sequence_index, element_index)
    let mut heap = BinaryHeap::new();

    // Initialize heap with first element from each sequence
    for (seq_idx, seq) in sequences.iter().enumerate() {
        if let Some(first) = seq.first() {
            heap.push(Reverse((first.clone(), seq_idx, 0)));
        }
    }

    // Extract minimum and push next from same sequence
    while let Some(Reverse((value, seq_idx, elem_idx))) = heap.pop() {
        result.push(value);

        let next_idx = elem_idx + 1;
        if next_idx < sequences[seq_idx].len() {
            let next_val = sequences[seq_idx][next_idx].clone();
            heap.push(Reverse((next_val, seq_idx, next_idx)));
        }
    }

    result
}
}

Implementation Milestone 5: Insert algorithm:

#![allow(unused)]
fn main() {
pub fn insert(&mut self, value: T) -> bool {
    // Find insertion position using binary search
    match self.data.binary_search(&value) {
        Ok(_) => false,  // Already exists
        Err(pos) => {
            self.data.insert(pos, value);  // Insert at correct position
            true
        }
    }
}
}

Remove algorithm:

#![allow(unused)]
fn main() {
pub fn remove(&mut self, value: &T) -> bool {
    match self.data.binary_search(value) {
        Ok(pos) => {
            self.data.remove(pos);  // Found, remove it
            true
        }
        Err(_) => false  // Not found
    }
}
}

Contains (fast O(log n) lookup):

#![allow(unused)]
fn main() {
pub fn contains(&self, value: &T) -> bool {
    self.data.binary_search(value).is_ok()
}
}

Range query:

#![allow(unused)]
fn main() {
pub fn range(&self, start: &T, end: &T) -> &[T] {
    let lower = binary_search_lower_bound(&self.data, start);
    let upper = binary_search_upper_bound(&self.data, end);
    &self.data[lower..upper]
}
}

Implementation Milestone 6:

#![allow(unused)]
fn main() {
pub struct CollectionBenchmark {
    sizes: Vec<usize>,
}

impl CollectionBenchmark {
    pub fn benchmark_inserts(&self) {
        for &size in &self.sizes {
            // Test SortedVec
            let start = Instant::now();
            let mut sv = SortedVec::new();
            for i in 0..size {
                sv.insert(i);
            }
            let sv_time = start.elapsed();

            // Test BTreeSet
            let start = Instant::now();
            let mut bt = BTreeSet::new();
            for i in 0..size {
                bt.insert(i);
            }
            let bt_time = start.elapsed();

            // Test HashSet
            let start = Instant::now();
            let mut hs = HashSet::new();
            for i in 0..size {
                hs.insert(i);
            }
            let hs_time = start.elapsed();

            println!("Size {}: SV={:?}, BT={:?}, HS={:?}",
                     size, sv_time, bt_time, hs_time);
        }
    }
}

pub fn recommend_collection(
    size: usize,
    needs_ordering: bool,
    needs_ranges: bool,
    write_heavy: bool,
) -> &'static str {
    if !needs_ordering && !needs_ranges {
        return "HashSet";  // Fast, no ordering needed
    }

    if needs_ranges {
        if size < 1000 && !write_heavy {
            return "SortedVec";  // Cache-friendly for small sizes
        }
        return "BTreeSet";  // Better for large or write-heavy
    }

    if size < 1000 {
        "SortedVec"
    } else {
        "BTreeSet"
    }
}
}

Complete Working Example

use std::cmp::Ordering;
use std::cmp::Reverse;
use std::collections::{BTreeSet, BinaryHeap, HashSet};

// =============================================================================
// Milestone 1: Binary Search Variants
// =============================================================================

pub fn binary_search_exact<T: Ord>(arr: &[T], target: &T) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;
        match arr[mid].cmp(target) {
            Ordering::Equal => return Some(mid),
            Ordering::Less => left = mid + 1,
            Ordering::Greater => right = mid,
        }
    }
    None
}

pub fn binary_search_lower_bound<T: Ord>(arr: &[T], target: &T) -> usize {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;
        if arr[mid] < *target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    left
}

pub fn binary_search_upper_bound<T: Ord>(arr: &[T], target: &T) -> usize {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;
        if arr[mid] <= *target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    left
}

pub fn is_sorted<T: Ord>(arr: &[T]) -> bool {
    arr.windows(2).all(|w| w[0] <= w[1])
}

// =============================================================================
// Milestone 2: Range Queries with Binary Search
// =============================================================================

pub fn range_query<'a, T: Ord>(arr: &'a [T], start: &T, end: &T) -> &'a [T] {
    if arr.is_empty() || start > end {
        return &arr[0..0];
    }
    let begin = binary_search_lower_bound(arr, start);
    let end_idx = binary_search_upper_bound(arr, end);
    &arr[begin.min(arr.len())..end_idx.min(arr.len())]
}

pub fn count_in_range<T: Ord>(arr: &[T], start: &T, end: &T) -> usize {
    if start > end {
        return 0;
    }
    let begin = binary_search_lower_bound(arr, start);
    let end_idx = binary_search_upper_bound(arr, end);
    end_idx.saturating_sub(begin)
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LogEntry {
    pub timestamp: u64,
    pub level: String,
    pub message: String,
}

impl Ord for LogEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        self.timestamp.cmp(&other.timestamp)
    }
}

impl PartialOrd for LogEntry {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

pub fn query_logs_by_time(logs: &[LogEntry], start_time: u64, end_time: u64) -> &[LogEntry] {
    let start = LogEntry {
        timestamp: start_time,
        level: String::new(),
        message: String::new(),
    };
    let end = LogEntry {
        timestamp: end_time,
        level: String::new(),
        message: String::new(),
    };
    range_query(logs, &start, &end)
}

// =============================================================================
// Milestone 3: Auto-Complete with Prefix Matching
// =============================================================================

pub fn prefix_search<'a>(words: &'a [String], prefix: &str) -> &'a [String] {
    if prefix.is_empty() {
        return words;
    }
    let start = words.partition_point(|word| word.as_str() < prefix);
    let mut end = start;
    while end < words.len() && words[end].starts_with(prefix) {
        end += 1;
    }
    &words[start..end]
}

#[derive(Debug)]
pub struct AutoComplete {
    words: Vec<String>,
}

impl AutoComplete {
    pub fn new(mut words: Vec<String>) -> Self {
        words.sort();
        words.dedup();
        Self { words }
    }

    pub fn suggest(&self, prefix: &str) -> Vec<&str> {
        let matches = prefix_search(&self.words, prefix);
        matches.iter().take(10).map(|s| s.as_str()).collect()
    }

    pub fn suggest_all(&self, prefix: &str) -> Vec<&str> {
        prefix_search(&self.words, prefix)
            .iter()
            .map(|s| s.as_str())
            .collect()
    }

    pub fn word_count(&self) -> usize {
        self.words.len()
    }
}

// =============================================================================
// Milestone 4: Merge Sorted Sequences (K-Way Merge)
// =============================================================================

pub fn merge_two<T: Ord + Clone>(left: &[T], right: &[T]) -> Vec<T> {
    let mut result = Vec::with_capacity(left.len() + right.len());
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            result.push(left[i].clone());
            i += 1;
        } else {
            result.push(right[j].clone());
            j += 1;
        }
    }
    if i < left.len() {
        result.extend_from_slice(&left[i..]);
    }
    if j < right.len() {
        result.extend_from_slice(&right[j..]);
    }
    result
}

pub fn merge_k<T: Ord + Clone>(sequences: &[&[T]]) -> Vec<T> {
    if sequences.is_empty() {
        return Vec::new();
    }
    let total_len: usize = sequences.iter().map(|seq| seq.len()).sum();
    let mut result = Vec::with_capacity(total_len);
    let mut heap: BinaryHeap<Reverse<(T, usize, usize)>> = BinaryHeap::new();

    for (seq_idx, seq) in sequences.iter().enumerate() {
        if let Some(first) = seq.first() {
            heap.push(Reverse((first.clone(), seq_idx, 0)));
        }
    }

    while let Some(Reverse((value, seq_idx, elem_idx))) = heap.pop() {
        result.push(value);
        let next_idx = elem_idx + 1;
        if let Some(next_val) = sequences[seq_idx].get(next_idx) {
            heap.push(Reverse((next_val.clone(), seq_idx, next_idx)));
        }
    }

    result
}

pub struct MergeIterator<'a, T> {
    sequences: Vec<&'a [T]>,
    indices: Vec<usize>,
    heap: BinaryHeap<Reverse<(T, usize)>>,
}

impl<'a, T: Ord + Clone> MergeIterator<'a, T> {
    pub fn new(sequences: Vec<&'a [T]>) -> Self {
        let mut heap = BinaryHeap::new();
        let mut indices = vec![0; sequences.len()];
        for (seq_idx, seq) in sequences.iter().enumerate() {
            if let Some(first) = seq.first() {
                heap.push(Reverse((first.clone(), seq_idx)));
            }
        }
        Self {
            sequences,
            indices,
            heap,
        }
    }
}

impl<'a, T: Ord + Clone> Iterator for MergeIterator<'a, T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let Reverse((value, seq_idx)) = self.heap.pop()?;
        self.indices[seq_idx] += 1;
        if let Some(next_val) = self.sequences[seq_idx].get(self.indices[seq_idx]) {
            self.heap
                .push(Reverse((next_val.clone(), seq_idx)));
        }
        Some(value)
    }
}

// =============================================================================
// Milestone 5: Sorted Set with Incremental Updates
// =============================================================================

#[derive(Debug, Clone)]
pub struct SortedVec<T> {
    data: Vec<T>,
}

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

    pub fn insert(&mut self, value: T) -> bool {
        match self.data.binary_search(&value) {
            Ok(_) => false,
            Err(idx) => {
                self.data.insert(idx, value);
                true
            }
        }
    }

    pub fn remove(&mut self, value: &T) -> bool {
        if let Ok(idx) = self.data.binary_search(value) {
            self.data.remove(idx);
            true
        } else {
            false
        }
    }

    pub fn contains(&self, value: &T) -> bool {
        self.data.binary_search(value).is_ok()
    }

    pub fn range(&self, start: &T, end: &T) -> &[T] {
        range_query(&self.data, start, end)
    }

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

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

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

// =============================================================================
// Milestone 6: Performance Optimization and Trade-offs
// =============================================================================

pub struct CollectionBenchmark {
    sizes: Vec<usize>,
}

impl CollectionBenchmark {
    pub fn new(sizes: Vec<usize>) -> Self {
        Self { sizes }
    }

    pub fn benchmark_inserts(&self) {
        for &size in &self.sizes {
            let mut sorted_vec = SortedVec::new();
            let mut btree = BTreeSet::new();
            let mut hash = HashSet::new();
            for i in 0..size {
                sorted_vec.insert(i);
                btree.insert(i);
                hash.insert(i);
            }
            println!("Inserted {} elements", size);
            assert_eq!(sorted_vec.len(), size);
            assert_eq!(btree.len(), size);
            assert_eq!(hash.len(), size);
        }
    }

    pub fn benchmark_lookups(&self) {
        for &size in &self.sizes {
            let data: Vec<i32> = (0..size as i32).collect();
            let mut sorted_vec = SortedVec::new();
            for &v in &data {
                sorted_vec.insert(v);
            }
            let btree: BTreeSet<_> = data.iter().copied().collect();
            let hash: HashSet<_> = data.iter().copied().collect();
            for &key in &[0, size as i32 / 2, size as i32 - 1] {
                sorted_vec.contains(&key);
                btree.contains(&key);
                hash.contains(&key);
            }
        }
    }

    pub fn benchmark_ranges(&self) {
        for &size in &self.sizes {
            let mut sorted_vec = SortedVec::new();
            for i in 0..size {
                sorted_vec.insert(i);
            }
            let btree: BTreeSet<_> = (0..size).collect();
            let sv_range = sorted_vec.range(&10, &20);
            let bt_range: Vec<_> = btree.range(10..=20).collect();
            assert_eq!(sv_range.len(), bt_range.len());
        }
    }

    pub fn measure_memory(&self) {
        for &size in &self.sizes {
            println!("Estimated memory for size {}: SortedVec={} bytes, BTreeSet={}, HashSet={}",
                size,
                size * std::mem::size_of::<usize>(),
                size * (std::mem::size_of::<usize>() * 2),
                size * (std::mem::size_of::<usize>() * 3));
        }
    }

    pub fn generate_report(&self) {
        println!("Collection Benchmark Report");
        for &size in &self.sizes {
            println!("- Tested size {}", size);
        }
    }
}

pub fn recommend_collection(
    size: usize,
    needs_ordering: bool,
    needs_ranges: bool,
    write_heavy: bool,
) -> &'static str {
    if !needs_ordering && !needs_ranges {
        return "HashSet";
    }
    if size > 1000 || write_heavy {
        return "BTreeSet";
    }
    if needs_ranges {
        "SortedVec"
    } else {
        "BTreeSet"
    }
}

// =============================================================================
// Tests
// =============================================================================

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

    // Milestone 1 tests
    #[test]
    fn test_exact_search_found() {
        let arr = vec![1, 3, 5, 7, 9, 11, 13];
        assert_eq!(binary_search_exact(&arr, &5), Some(2));
        assert_eq!(binary_search_exact(&arr, &1), Some(0));
        assert_eq!(binary_search_exact(&arr, &13), Some(6));
    }

    #[test]
    fn test_exact_search_not_found() {
        let arr = vec![1, 3, 5, 7, 9];
        assert_eq!(binary_search_exact(&arr, &2), None);
        assert_eq!(binary_search_exact(&arr, &0), None);
        assert_eq!(binary_search_exact(&arr, &10), None);
    }

    #[test]
    fn test_lower_upper_bounds() {
        let arr = vec![1, 3, 5, 7, 9];
        assert_eq!(binary_search_lower_bound(&arr, &5), 2);
        assert_eq!(binary_search_lower_bound(&arr, &4), 2);
        assert_eq!(binary_search_upper_bound(&arr, &5), 3);
        assert_eq!(binary_search_upper_bound(&arr, &4), 2);
    }

    #[test]
    fn test_is_sorted() {
        assert!(is_sorted(&[1, 2, 3]));
        assert!(is_sorted(&[1, 1, 2]));
        assert!(!is_sorted(&[2, 1, 3]));
    }

    // Milestone 2 tests
    #[test]
    fn test_range_query_basic() {
        let arr = vec![1, 3, 5, 7, 9, 11, 13];
        let result = range_query(&arr, &5, &11);
        assert_eq!(result, &[5, 7, 9, 11]);
    }

    #[test]
    fn test_range_query_empty() {
        let arr = vec![1, 3, 5, 7, 9];
        let result = range_query(&arr, &20, &30);
        assert!(result.is_empty());
    }

    #[test]
    fn test_count_in_range() {
        let arr = vec![1, 3, 5, 7, 9, 11, 13, 15];
        assert_eq!(count_in_range(&arr, &5, &11), 4);
    }

    #[test]
    fn test_query_logs() {
        let logs = vec![
            LogEntry { timestamp: 100, level: "INFO".into(), message: "Msg1".into() },
            LogEntry { timestamp: 200, level: "INFO".into(), message: "Msg2".into() },
            LogEntry { timestamp: 300, level: "ERROR".into(), message: "Msg3".into() },
        ];
        let result = query_logs_by_time(&logs, 150, 250);
        assert_eq!(result.len(), 1);
        assert_eq!(result[0].timestamp, 200);
    }

    // Milestone 3 tests
    #[test]
    fn test_prefix_search_basic() {
        let words = vec![
            "apple".to_string(),
            "application".to_string(),
            "apply".to_string(),
            "banana".to_string(),
        ];
        let result = prefix_search(&words, "app");
        assert_eq!(result.len(), 3);
    }

    #[test]
    fn test_autocomplete() {
        let words = vec![
            "apple".to_string(),
            "application".to_string(),
            "apply".to_string(),
            "appreciate".to_string(),
            "banana".to_string(),
        ];
        let ac = AutoComplete::new(words);
        let suggestions = ac.suggest("app");
        assert!(suggestions.len() <= 10);
        assert!(suggestions.iter().all(|s| s.starts_with("app")));
    }

    #[test]
    fn test_autocomplete_dedup() {
        let words = vec!["apple".to_string(), "apple".to_string()];
        let ac = AutoComplete::new(words);
        assert_eq!(ac.word_count(), 1);
    }

    // Milestone 4 tests
    #[test]
    fn test_merge_two_basic() {
        let left = vec![1, 3, 5];
        let right = vec![2, 4, 6];
        let result = merge_two(&left, &right);
        assert_eq!(result, vec![1, 2, 3, 4, 5, 6]);
    }

    #[test]
    fn test_merge_k_basic() {
        let seq1 = vec![1, 4, 7];
        let seq2 = vec![2, 5, 8];
        let seq3 = vec![3, 6, 9];
        let sequences = vec![&seq1[..], &seq2[..], &seq3[..]];
        let result = merge_k(&sequences);
        assert_eq!(result, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    }

    #[test]
    fn test_merge_iterator() {
        let seq1 = vec![1, 4, 7];
        let seq2 = vec![2, 5, 8];
        let seq3 = vec![3, 6, 9];
        let sequences = vec![&seq1[..], &seq2[..], &seq3[..]];
        let iter = MergeIterator::new(sequences);
        let result: Vec<_> = iter.collect();
        assert_eq!(result, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    }

    #[test]
    fn test_merge_performance() {
        use std::time::Instant;
        let sequences: Vec<Vec<i32>> = (0..10)
            .map(|i| (i..1000).step_by(10).collect())
            .collect();
        let seq_refs: Vec<&[i32]> = sequences.iter().map(|seq| seq.as_slice()).collect();
        let start = Instant::now();
        let _ = merge_k(&seq_refs);
        let k_time = start.elapsed();
        let start = Instant::now();
        let mut merged = sequences[0].clone();
        for seq in &sequences[1..] {
            merged = merge_two(&merged, seq);
        }
        let two_time = start.elapsed();
        println!("K-way: {:?}, two-way: {:?}", k_time, two_time);
    }

    // Milestone 5 tests
    #[test]
    fn test_sorted_vec_insert() {
        let mut sv = SortedVec::new();
        assert!(sv.insert(5));
        assert!(sv.insert(3));
        assert!(sv.insert(7));
        assert_eq!(sv.as_slice(), &[3, 5, 7]);
    }

    #[test]
    fn test_sorted_vec_remove() {
        let mut sv = SortedVec::new();
        sv.insert(1);
        sv.insert(3);
        sv.insert(5);
        assert!(sv.remove(&3));
        assert_eq!(sv.as_slice(), &[1, 5]);
    }

    #[test]
    fn test_sorted_vec_range() {
        let mut sv = SortedVec::new();
        for value in &[1, 3, 5, 7, 9, 11] {
            sv.insert(*value);
        }
        assert_eq!(sv.range(&5, &9), &[5, 7, 9]);
    }

    #[test]
    fn test_sorted_vec_contains() {
        let mut sv = SortedVec::new();
        sv.insert(1);
        sv.insert(3);
        assert!(sv.contains(&3));
        assert!(!sv.contains(&5));
    }

    // Milestone 6 tests
    #[test]
    fn test_recommendations() {
        assert_eq!(recommend_collection(100, true, true, false), "SortedVec");
        assert_eq!(recommend_collection(10000, true, false, false), "BTreeSet");
        assert_eq!(recommend_collection(1000, false, false, true), "HashSet");
    }

    #[test]
    fn test_benchmark_suite() {
        let benchmark = CollectionBenchmark::new(vec![100, 1000]);
        benchmark.benchmark_inserts();
        benchmark.benchmark_lookups();
        benchmark.benchmark_ranges();
        benchmark.measure_memory();
        benchmark.generate_report();
    }

    #[test]
    fn test_cache_locality() {
        use std::time::Instant;
        let n: usize = 10000;
        let data: Vec<i32> = (0..n as i32).collect();
        let start = Instant::now();
        let sum_seq: i32 = data.iter().sum();
        let seq_time = start.elapsed();
        let indices: Vec<usize> = (0..n).rev().collect();
        let start = Instant::now();
        let sum_rand: i32 = indices.iter().map(|&i| data[i]).sum();
        let rand_time = start.elapsed();
        assert_eq!(sum_seq, sum_rand);
        println!("Sequential: {:?}, Random: {:?}", seq_time, rand_time);
    }
}

fn main() {}

Project-Wide Benefits

Binary search applications throughout project:

End-to-end comparison (typical workload):

Real-world systems using binary search:

When to use sorted data + binary search:

• ✅ Read-heavy workloads: Many searches, few updates
• ✅ Range queries needed: Find all in [start, end]
• ✅ Ordered iteration: Process in sorted order
• ✅ Predictable performance: O(log n) guaranteed
• ❌ Write-heavy: Use hash table instead
• ❌ No ordering needed: Use HashSet
• ❌ Complex queries: Use database