Binary search

About This Module

This module introduces the binary search algorithm, a fundamental technique for efficiently finding elements in sorted collections. You'll learn how binary search works, its time complexity, and how to implement it in Rust. The module also covers practical applications of binary search and common pitfalls to avoid.

Prework

Prework Reading

Please read the following sections from The Rust Programming Language Book:

• Chapter 3.2: Guessing Game - Focus on input handling and basic control flow
• Chapter 4.1: Ownership - Understand how Rust manages memory
• Chapter 4.2: References and Borrowing - Learn about references, mutable references, and borrowing rules
• Chapter 4.3: The Slice Type - Understand slices and how they relate to arrays and vectors

Pre-lecture Reflections

Before class, consider these questions:

1. What is the time complexity of binary search, and how does it compare to linear search?
2. How does Rust's ownership and borrowing system impact the implementation of algorithms like binary search?
3. What are some common pitfalls when implementing binary search, and how can they be avoided?
4. How can binary search be adapted for different data structures, such as linked lists or trees?

Lecture

Learning Objectives

By the end of this module, you will be able to:

• Understand the binary search algorithm and its time complexity
• Implement binary search in Rust
• Apply binary search to solve practical problems
• Recognize common pitfalls and edge cases in binary search implementations

Binary Search

Input: sorted array/vector v

Task: find if a specific element x appears in it

General strategy:

• maintain range left..right within v of where x could be
• repeat:
  • ask about the middle of the range
  • if x found, celebrate
  • if the middle element $<$ x, narrow search to the right half
  • otherwise, narrow search to the left half

Let's implement it!

Might be harder than you think!

Jon Bentley in "Programming pearls" claims that only 10% programmers succeed, even given unlimited amount of time

Ad:

• Great book if you are interested in programming and basic algorithms
• First edition mostly uses pseudocode
• 2nd edition focused on C++ (probably still great)
• very cheap if you want to buy second hand (< $10)

Let's implement it!

/// Employ binary search on a sorted vector to find a value
///
/// # Arguments
///
/// * data:&[i32] -- sorted array
///
/// # Returns
///
/// * Option<(usize, i32)> -- Tuple of index and value
fn present(mut data:&[i32], element:i32) -> Option<(usize,i32)> {
    let (mut left, mut right) = (0, data.len());
    // invariant: if element has not been found, it must be in data[left..right]
    while left < right {
        let middle = (left+right)/2;
        if data[middle] == element {
            return Some((middle, element));
        } else if data[middle] > element {
            right = middle - 1 
        } else {
            left = middle + 1
        }
    }
    None
}

let v = vec![-16,-4,0,2,4,12,32,48,48,111];

present(&v, 111)

Some((9, 111))

present(&v, 5)

None

present(&v, 1000)

None

present(&v, 32)

Some((6, 32))

Technical Coding Challenge

Coding Challenge

Coding Challenge Review