Algorithms & Slices

Rust Binary Search (Custom Implementation & slice::binary_search)

Implement an idiomatic binary search algorithm in Rust returning Option<usize> and compare it with the standard library slice method.

Rust Source Code

Editable code sample with line numbers

Rust

fn custom_binary_search<T: Ord>(slice: &[T], target: &T) -> Option<usize> {
    if slice.is_empty() {
        return None;
    }

let mut left = 0;
    let mut right = slice.len() - 1;

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

match slice[mid].cmp(target) {
            std::cmp::Ordering::Equal => return Some(mid),
            std::cmp::Ordering::Less => left = mid + 1,
            std::cmp::Ordering::Greater => {
                if mid == 0 {
                    break;
                }
                right = mid - 1;
            }
        }
    }

None
}

fn main() {
    let sorted_vec = vec![4, 8, 15, 16, 23, 42, 58, 73, 99];
    let target = 23;

println!("Array: {:?}", sorted_vec);

match custom_binary_search(&sorted_vec, &target) {
        Some(idx) => println!("Custom Binary Search: Found {} at index {}", target, idx),
        None => println!("Custom Binary Search: Target not found"),
    }

// Standard Library slice::binary_search
    match sorted_vec.binary_search(&target) {
        Ok(idx) => println!("slice::binary_search: Found at index {}", idx),
        Err(insert_idx) => println!("slice::binary_search: Not found, could be inserted at {}", insert_idx),
    }
}

Expected Output

When this program is compiled and executed, the terminal outputs:

Array: [4, 8, 15, 16, 23, 42, 58, 73, 99]
Custom Binary Search: Found 23 at index 4
slice::binary_search: Found at index 4

How the Code Works

Rust uses unsigned integer types (usize) for array indexing. To prevent integer underflow when decrementing right when mid == 0, we explicitly check if mid == 0 before subtracting. We utilize generic trait bounds <T: Ord> so any type implementing the Ord trait can be searched. Pattern matching with std::cmp::Ordering makes comparison branch logic clean and compiler-verified.

Time Complexity

O(log N)

Space Complexity

O(1)

Key Takeaways & Best Practices

Rust slice indexing requires usize, requiring care against underflow when right = mid - 1.
Trait bounds like T: Ord enable zero-cost generic algorithms.
slice::binary_search returns Result<usize, usize> indicating index or insertion point.

Master Rust with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related Rust Examples

Concurrency & Memory

O(NumThreads)

Rust Thread-Safe Counter (Arc & Mutex)

Safely mutate shared data across multiple OS threads in Rust using Arc (Atomic Reference Counting) and Mutex synchronization.

Runnable Code

View Code

Data Structures & Generics

O(1) amortized for push, pop, and peek

Rust Generic Stack Data Structure

Implement a type-safe generic LIFO stack data structure in Rust with peek, push, pop, and empty check capabilities.

Rust QuickSort on Mutable Slices

Implement in-place QuickSort sorting in Rust on mutable slices (&mut [T]) using generic trait bounds and safe borrow checking.

Runnable Code

View Code

How the Code Works

Time Complexity

O(log N)

Space Complexity

O(1)

Key Takeaways & Best Practices

Rust slice indexing requires usize, requiring care against underflow when right = mid - 1.
Trait bounds like T: Ord enable zero-cost generic algorithms.
slice::binary_search returns Result<usize, usize> indicating index or insertion point.

Rust Binary Search (Custom Implementation & slice::binary_search)

Rust Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master Rust with ZenCompiler

Related Rust Examples

Rust Thread-Safe Counter (Arc & Mutex)

Rust Generic Stack Data Structure

Rust QuickSort on Mutable Slices

Platform & Tools

Account

Company & Help

Legal & Policies

Rust Binary Search (Custom Implementation & slice::binary_search)

Rust Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master Rust with ZenCompiler

Related Rust Examples

Rust Thread-Safe Counter (Arc & Mutex)

Rust Generic Stack Data Structure

Rust QuickSort on Mutable Slices