Why Binary Search and What Sorted Order Gives You in DSA Rust - Why It Works

Concept Flow - Why Binary Search and What Sorted Order Gives You

Start with sorted array

↓

Set low = 0, high = length-1

↓

Calculate mid = (low + high) / 2

↓

Compare target with array[mid

↓

high=mid-1

↓

Repeat until low > high

↓

Not found

Binary search works on sorted arrays by repeatedly dividing the search range in half, quickly narrowing down where the target value could be.

Execution Sample

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) / 2;
        if arr[mid] == target {
            return Some(mid);
        } else if arr[mid] < target {
            low = mid + 1;
        } else {
            high = mid.wrapping_sub(1);
        }
    }
    None
}

This code searches for a target number in a sorted array by checking the middle element and adjusting the search range until it finds the target or concludes it is not present.

Execution Table

Step	Operation	low	high	mid	Compare arr[mid] with target	Action	Array State (indices:values)
1	Initialize	0	6	-	-	Set low=0, high=6	[0:1, 1:3, 2:5, 3:7, 4:9, 5:11, 6:13]
2	Calculate mid	0	6	3	arr[3]=7 vs target=9	7 < 9 → low=mid+1=4	[0:1, 1:3, 2:5, 3:7, 4:9, 5:11, 6:13]
3	Calculate mid	4	6	5	arr[5]=11 vs target=9	11 > 9 → high=mid-1=4	[0:1, 1:3, 2:5, 3:7, 4:9, 5:11, 6:13]
4	Calculate mid	4	4	4	arr[4]=9 vs target=9	Found target at index 4	[0:1, 1:3, 2:5, 3:7, 4:9, 5:11, 6:13]
5	Exit	4	4	4	Target found	Return index 4	[0:1, 1:3, 2:5, 3:7, 4:9, 5:11, 6:13]

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
low	0	4	4	4	4
high	6	6	4	4	4
mid	-	3	5	4	4

Key Moments - 3 Insights

Why must the array be sorted for binary search to work?

Because binary search decides which half to search next by comparing the target with the middle element. If the array is not sorted, these decisions are invalid. See execution_table steps 2 and 3 where the search range changes based on comparisons.

Why do we update 'low' to mid + 1 and 'high' to mid - 1?

Because after checking mid, if the target is greater, it can't be at mid or before, so we move low to mid + 1. If smaller, it can't be at mid or after, so we move high to mid - 1. This narrows the search range correctly as shown in execution_table steps 2 and 3.

What happens if the target is not in the array?

The loop continues adjusting low and high until low > high, meaning the search range is empty. Then the function returns None. This is the exit condition after step 5 if no match is found.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 3?

A 5

B 3

C 4

D 6

💡 Hint

Check the 'mid' column in execution_table row for step 3.

At which step does the search range narrow to a single element?

A Step 2

B Step 4

C Step 1

D Step 3

💡 Hint

Look at 'low' and 'high' values in execution_table; when low equals high, the range has one element.

If the array was not sorted, how would the binary search behave?

A It would still find the target correctly

B It would run faster

C It might miss the target or give wrong results

D It would return the first element always

💡 Hint

Refer to key_moments about why sorting is necessary for correct decisions.

Concept Snapshot

Binary Search requires a sorted array.
Start with low=0 and high=array length-1.
Find mid = (low + high) / 2.
Compare target with arr[mid].
If equal, return mid.
If target > arr[mid], search right half (low=mid+1).
Else search left half (high=mid-1).
Repeat until low > high (not found).

Full Transcript

Binary search is a fast way to find a number in a sorted list. We start by looking at the middle number. If it matches our target, we are done. If the target is bigger, we look only in the right half. If smaller, we look only in the left half. We keep cutting the search area in half until we find the target or run out of places to look. This only works if the list is sorted because we rely on order to decide which half to search next.

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