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

Why Binary Search and What Sorted Order Gives You

📖 Scenario: Imagine you have a list of book titles sorted alphabetically on a shelf. You want to find if a certain book is there quickly without checking every book one by one.

🎯 Goal: You will create a sorted list of book titles, set a target book to find, use binary search to check if the book is in the list, and print the result.

📋 What You'll Learn

Create a sorted vector of book titles called books with these exact entries: "Algorithms", "Data Structures", "Networking", "Operating Systems", "Rust Programming"

Create a variable called target and set it to "Networking"

Use the binary_search method on books with target to find the book

Print "Found" if the book is in the list, otherwise print "Not Found"

💡 Why This Matters

🌍 Real World

Binary search is used in many software systems to quickly find items in sorted data, like searching contacts, files, or database indexes.

💼 Career

Understanding binary search and the importance of sorted data is fundamental for software developers, data engineers, and anyone working with efficient data retrieval.

1

Create a sorted list of book titles

Create a vector called books with these exact strings in this order: "Algorithms", "Data Structures", "Networking", "Operating Systems", "Rust Programming"

DSA Rust

# Create the vector books with the given titles
# Your code here

Hint

Use let books = vec![...] with the exact titles in order.

2

Set the target book to find

Create a variable called target and set it to the string "Networking"

DSA Rust

fn main() {
    let books = vec!["Algorithms", "Data Structures", "Networking", "Operating Systems", "Rust Programming"];
    // Create target variable here
    # Your code here
}

Hint

Use let target = "Networking"; to create the variable.

3

Use binary search to find the target book

Use books.binary_search(&target) and store the result in a variable called result

DSA Rust

fn main() {
    let books = vec!["Algorithms", "Data Structures", "Networking", "Operating Systems", "Rust Programming"];
    let target = "Networking";
    // Use binary_search and store in result
    # Your code here
}

Hint

Use let result = books.binary_search(&target); to perform the search.

4

Print if the book was found or not

Use an if statement to check if result.is_ok() is true. If yes, print "Found", else print "Not Found"

DSA Rust

fn main() {
    let books = vec!["Algorithms", "Data Structures", "Networking", "Operating Systems", "Rust Programming"];
    let target = "Networking";
    let result = books.binary_search(&target);
    // Print Found or Not Found based on result
    # Your code here
}

Hint

Use if result.is_ok() { println!("Found"); } else { println!("Not Found"); }

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