Why Binary Search and What Sorted Order Gives You in DSA Rust - Why This Pattern

Mental Model

Binary search quickly finds a value by cutting the search area in half each time, but it only works if the list is sorted.

Analogy: Imagine looking for a word in a dictionary: you open near the middle, decide if your word is before or after, then open the middle of that half, repeating until you find it.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Pointers: low ↑ middle ↑ high ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], search for 9

Goal: Find the position of 9 quickly using binary search

Step 1: Set low to index 0, high to index 6, find middle at index 3 (value 7)

[1] -> [3] -> [5] -> [7] ↑middle, low=0 ↑, high=6 ↑ -> [9] -> [11] -> [13] -> null

Why: We start by checking the middle to decide which half to search next

Step 2: Since 9 > 7, move low to middle + 1 = 4

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
low=4 ↑, high=6 ↑, middle=5 (value 11) ↑

Why: We discard the left half because 9 is greater than 7

Step 3: Since 9 < 11, move high to middle - 1 = 4

[1] -> [3] -> [5] -> [7] -> [9] ↑low=4, high=4 ↑middle=4 (value 9)

Why: We discard the right half because 9 is less than 11

Step 4: Check middle value 9 equals target 9, found at index 4

[1] -> [3] -> [5] -> [7] -> [9] ↑found at index 4 -> [11] -> [13] -> null

Why: We found the target value, so we stop

Result:

[1] -> [3] -> [5] -> [7] -> [9] ↑found at index 4 -> [11] -> [13] -> null
Answer: index 4

Annotated Code

DSA Rust

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len().wrapping_sub(1);
    while low <= high {
        let mid = low + (high - low) / 2; // find middle index
        if arr[mid] == target {
            return Some(mid); // found target
        } else if arr[mid] < target {
            low = mid + 1; // search right half
        } else {
            high = mid.wrapping_sub(1); // search left half
        }
    }
    None // target not found
}

fn main() {
    let arr = [1, 3, 5, 7, 9, 11, 13];
    let target = 9;
    match binary_search(&arr, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found", target),
    }
}

let mid = low + (high - low) / 2; // find middle index

calculate middle index to split search range

if arr[mid] == target { return Some(mid); }

check if middle element is target

else if arr[mid] < target { low = mid + 1; }

move low pointer to right half if target is greater

else { high = mid.wrapping_sub(1); }

move high pointer to left half if target is smaller

Output

Found 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Linear search is O(n) because it checks each element one by one, which is slower for large sorted lists

Edge Cases

empty array

returns None immediately because high < low

DSA Rust

while low <= high {

target smaller than all elements

search narrows and returns None after checking all halves

DSA Rust

while low <= high {

target larger than all elements

search narrows and returns None after checking all halves

DSA Rust

while low <= high {

When to Use This Pattern

When you need to find an item quickly in a sorted list, reach for binary search because it cuts the search area in half each step, making it very fast.

Common Mistakes

Mistake: Not ensuring the list is sorted before binary search
Fix: Always sort the list first or confirm it is sorted before applying binary search

Mistake: Calculating middle index as (low + high) which can overflow
Fix: Calculate middle as low + (high - low) / 2 to avoid overflow

Mistake: Using while low < high instead of while low <= high, missing last element check
Fix: Use while low <= high to include all elements in search

Summary

Binary search finds a target value quickly by repeatedly dividing the search range in half.

Use binary search when you have a sorted list and want fast lookup.

The key insight is that sorted order lets you discard half the list each step, making search much faster.

Practice

1. Why is binary search only applicable on a sorted list?

easy

A. Because binary search works on unsorted lists by checking every element

B. Because binary search can only work on lists with unique elements

C. Because binary search divides the list and compares middle elements, which only works if the list is sorted

D. Because binary search requires the list to be reversed

Solution

1. Step 1: Understand binary search method

   Binary search works by repeatedly dividing the list and comparing the middle element to the target.

2. Step 2: Importance of sorted order

   This division and comparison only make sense if the list is sorted, so we know which half to discard.

3. Final Answer:

   Because binary search divides the list and compares middle elements, which only works if the list is sorted -> Option C

4. Quick Check:

   Sorted list needed for binary search = True [OK]

Hint: Binary search needs sorted data to decide halves quickly [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Believing binary search requires unique elements
• Confusing binary search with linear search

2. Which of the following Rust code snippets correctly declares a sorted vector for binary search?

easy

A. let v = vec![1, 2, 3, 4];

B. let v = vec![3, 1, 4, 2];

C. let v = vec![4, 3, 2, 1];

D. let v = vec!["apple", "banana", "cherry"];

Solution

1. Step 1: Identify sorted vector

   Binary search requires the vector to be sorted in ascending order. let v = vec![1, 2, 3, 4]; is sorted ascending: 1, 2, 3, 4.

2. Step 2: Check other options

   let v = vec![3, 1, 4, 2]; is unsorted. let v = vec![4, 3, 2, 1]; is sorted descending, which is not standard for binary search. let v = vec!["apple", "banana", "cherry"]; is sorted alphabetically but contains strings, not integers.

3. Final Answer:

   let v = vec![1, 2, 3, 4]; -> Option A

4. Quick Check:

   Sorted vector for binary search = let v = vec![1, 2, 3, 4]; [OK]

Hint: Binary search needs ascending sorted vector [OK]

Common Mistakes:

• Using unsorted vectors for binary search
• Assuming descending order works without modification
• Mixing data types in vector

3. What will be the output of this Rust code using binary search on a sorted vector?

let v = vec![2, 4, 6, 8, 10];
let result = v.binary_search(&6);
println!("{:?}", result);

medium

A. Ok(2)

B. Ok(3)

C. Err(2)

D. Err(3)

Solution

1. Step 1: Understand binary_search return

   binary_search returns Ok(index) if found, Err(insert_pos) if not found.

2. Step 2: Find index of 6 in vector

   Vector is [2,4,6,8,10]. 6 is at index 2 (0-based).

3. Final Answer:

   Ok(2) -> Option A

4. Quick Check:

   Index of 6 = 2, so output = Ok(2) [OK]

Hint: binary_search returns Ok(index) if found [OK]

Common Mistakes:

• Confusing Ok and Err results
• Miscounting zero-based index
• Assuming Err means found

4. Identify the error in this Rust code that attempts binary search on an unsorted vector:

let v = vec![5, 3, 8, 1];
let result = v.binary_search(&3);
println!("{:?}", result);

medium

A. No error, code runs and returns Ok(1)

B. Logical error: vector is unsorted, so binary_search result is unreliable

C. No error, code runs but returns Err(1)

D. Syntax error: binary_search requires mutable vector

Solution

1. Step 1: Check vector order

   The vector is [5, 3, 8, 1], which is unsorted.

2. Step 2: Understand binary_search requirement

   binary_search requires sorted vectors; otherwise, the result is unpredictable or incorrect.

3. Final Answer:

   Logical error: vector is unsorted, so binary_search result is unreliable -> Option B

4. Quick Check:

   Unsorted vector breaks binary_search logic [OK]

Hint: Always sort vector before binary_search [OK]

Common Mistakes:

• Assuming binary_search works on unsorted vectors
• Confusing syntax errors with logical errors
• Thinking binary_search needs mutable vector

5. Given a sorted vector v = vec![1, 3, 5, 7, 9], how can you find the position to insert 6 to keep the vector sorted using binary search?

hard

A. Use v.binary_search(&6) which returns Ok(2)

B. Use v.iter().position(|&x| x > 6) which returns 2

C. Use v.binary_search(&6) which returns Err(2)

D. Use v.binary_search(&6) which returns Err(3)

Solution

1. Step 1: Understand binary_search return for missing element

   When element is not found, binary_search returns Err(insert_pos) where insert_pos is the index to insert to keep sorted order.

2. Step 2: Find insert position for 6 in vector

   Vector is [1,3,5,7,9]. 6 fits between 5 (index 2) and 7 (index 3), so insert position is 3.

3. Final Answer:

   Use v.binary_search(&6) which returns Err(3) -> Option D

4. Quick Check:

   Insert position for 6 = 3, so Err(3) returned [OK]

Hint: binary_search returns Err(insert_pos) if not found [OK]

Common Mistakes:

• Confusing Ok and Err results
• Misunderstanding insert position index
• Using iterator position instead of binary_search