Binary Search vs Linear Search Real Cost Difference in DSA C++ - Build Both Approaches

Binary Search vs Linear Search Real Cost Difference

📖 Scenario: You work in a library where you need to find books by their ID numbers. You want to compare two ways to find a book: looking one by one (linear search) and jumping to the middle and cutting the search area in half each time (binary search). This helps you understand which way is faster when the list is sorted.

🎯 Goal: You will create a list of book IDs, set a target book ID to find, write code to search for the book using both linear and binary search, and then print the number of steps each search took. This shows the real cost difference between the two methods.

📋 What You'll Learn

Create a sorted list of book IDs called book_ids with these exact values: 101, 203, 305, 407, 509, 611, 713, 815, 917, 1020

Create an integer variable called target_id and set it to 713

Write a linear search loop using for with iterator i to find target_id in book_ids and count steps in linear_steps

Write a binary search loop using while with variables left, right, and mid to find target_id in book_ids and count steps in binary_steps

Print the number of steps taken by linear search and binary search exactly as: Linear search steps: X and Binary search steps: Y

💡 Why This Matters

🌍 Real World

Searching sorted lists quickly is important in many applications like libraries, databases, and online stores.

💼 Career

Understanding search algorithms helps in optimizing software performance and is a common topic in coding interviews.

1

Create the list of book IDs

Create a sorted list of integers called book_ids with these exact values: 101, 203, 305, 407, 509, 611, 713, 815, 917, 1020

DSA C++

# Create the sorted list book_ids with the given values
# Your code here

Hint

Use an array of integers with the exact values in order.

2

Set the target book ID

Create an integer variable called target_id and set it to 713

DSA C++

int book_ids[] = {101, 203, 305, 407, 509, 611, 713, 815, 917, 1020};
// Set target_id to 713
# Your code here

Hint

Use a simple integer variable assignment.

3

Write linear search to count steps

Write a for loop with iterator i to search target_id in book_ids and count steps in linear_steps. Stop the loop when found.

DSA C++

int book_ids[] = {101, 203, 305, 407, 509, 611, 713, 815, 917, 1020};
int target_id = 713;
int linear_steps = 0;
// Write a for loop with i to find target_id and count steps in linear_steps
# Your code here

Hint

Loop through the array, increase steps, and stop when found.

4

Write binary search and print steps

Write a while loop using left, right, and mid to find target_id in book_ids and count steps in binary_steps. Then print the steps exactly as: Linear search steps: X and Binary search steps: Y

DSA C++

int book_ids[] = {101, 203, 305, 407, 509, 611, 713, 815, 917, 1020};
int target_id = 713;
int linear_steps = 0;
for (int i = 0; i < 10; i++) {
    linear_steps++;
    if (book_ids[i] == target_id) {
        break;
    }
}
int binary_steps = 0;
// Write binary search loop to find target_id and count steps in binary_steps
// Then print the steps as required
# Your code here

Hint

Use binary search logic and count each step. Then print the counts exactly.