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

Binary Search vs Linear Search Real Cost Difference

📖 Scenario: Imagine you have a list of product prices in a store. You want to find if a certain price exists in the list. You can look for it one by one (linear search) or use a faster method if the list is sorted (binary search). This project will help you see the difference in how many steps each method takes.

🎯 Goal: You will create a program that searches for a price in a list using both linear search and binary search. You will count and compare how many steps each search takes to find the price or decide it is not there.

📋 What You'll Learn

Create an array of integers with exact values

Create a variable to hold the target price to search

Implement linear search counting steps

Implement binary search counting steps

Print the number of steps taken by each search

💡 Why This Matters

🌍 Real World

Searching is a common task in many apps like shopping, contacts, or files. Knowing which search method is faster helps apps run smoothly.

💼 Career

Understanding search algorithms is important for software developers to write efficient code and optimize performance.

1

Create the price list array

Create an integer array called prices with these exact values: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100.

DSA C

int prices[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
// Your code here

Hint

Use curly braces to list all prices inside the array.

2

Set the target price to search

Create an integer variable called target and set it to 70.

DSA C

int prices[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int target = 70;
// Your code here

Hint

Use int target = 70; to set the price you want to find.

3

Implement linear search with step counting

Write a for loop using int i = 0; i < 10; i++ to search target in prices. Create an integer variable linear_steps initialized to 0. Increase linear_steps by 1 in each loop iteration. Stop the loop if prices[i] == target.

DSA C

int prices[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int target = 70;
int linear_steps = 0;
// Your code here

Hint

Count each step and stop when you find the target.

4

Implement binary search with step counting and print results

Implement binary search to find target in prices. Create int binary_steps = 0, int left = 0, and int right = 9. Use a while (left <= right) loop. Increase binary_steps by 1 each loop. Calculate mid = (left + right) / 2. If prices[mid] == target, break. If prices[mid] < target, set left = mid + 1. Else set right = mid - 1. Finally, print linear_steps and binary_steps with the exact format: printf("Linear search steps: %d\n", linear_steps); and printf("Binary search steps: %d\n", binary_steps);.

DSA C

int prices[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int target = 70;
int linear_steps = 0;
for (int i = 0; i < 10; i++) {
    linear_steps++;
    if (prices[i] == target) {
        break;
    }
}
int binary_steps = 0;
int left = 0;
int right = 9;
// Your code here
// Print the steps below

Hint

Binary search cuts the search space in half each step. Print the steps exactly as shown.

Practice

1. Which search algorithm generally performs faster on a sorted array of 1,000,000 elements?

easy

A. Depends on the element position only

B. Binary Search

C. Both perform equally

D. Linear Search

Solution

1. Step 1: Understand the search algorithms

   Binary Search divides the search space in half each step, while Linear Search checks elements one by one.

2. Step 2: Compare performance on large sorted arrays

   Binary Search takes about log2(1,000,000) ≈ 20 steps, Linear Search may take up to 1,000,000 steps.

3. Final Answer:

   Binary Search -> Option B

4. Quick Check:

   Binary Search is faster on sorted large arrays [OK]

Hint: Binary Search halves search space; Linear checks one by one [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted arrays
• Ignoring the array must be sorted for Binary Search
• Confusing average and worst-case times

2. Which of the following is the correct syntax to start a binary search loop in C for an array named arr with n elements?

easy

A. int start = 1, end = n; while (start < end) { ... }

B. int i = 0; while (i < n) { ... }

C. for (int i = 0; i <= n; i++) { ... }

D. int low = 0, high = n - 1; while (low <= high) { ... }

Solution

1. Step 1: Identify binary search loop boundaries

   Binary Search uses two pointers: low starting at 0 and high at n-1 (last index).

2. Step 2: Check loop condition correctness

   The loop continues while low is less than or equal to high to cover all elements.

3. Final Answer:

   int low = 0, high = n - 1; while (low <= high) { ... } -> Option D

4. Quick Check:

   Binary Search loop uses low <= high [OK]

Hint: Binary Search uses low=0, high=n-1, loop while low <= high [OK]

Common Mistakes:

• Using incorrect loop conditions like < or > only
• Starting indices from 1 instead of 0 in C arrays
• Using for loop without adjusting high pointer

3. What will be the output of the following C code snippet?

int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int target = 8;
int low = 0, high = n - 1, mid;
while (low <= high) {
    mid = (low + high) / 2;
    if (arr[mid] == target) {
        printf("Found at index %d", mid);
        break;
    } else if (arr[mid] < target) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

medium

A. Found at index 3

B. Found at index 2

C. Found at index 4

D. Not found

Solution

1. Step 1: Calculate mid and compare with target

   Initial low=0, high=4, mid=(0+4)/2=2, arr[2]=6 < 8, so low=mid+1=3.

2. Step 2: Next iteration mid and check

   Now low=3, high=4, mid=(3+4)/2=3, arr[3]=8 equals target, print index 3.

3. Final Answer:

   Found at index 3 -> Option A

4. Quick Check:

   Binary Search finds 8 at index 3 [OK]

Hint: Calculate mid each loop, adjust low/high accordingly [OK]

Common Mistakes:

• Using integer division incorrectly for mid
• Not updating low or high correctly
• Confusing array indices starting at 1

4. Identify the bug in this binary search code snippet in C:

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

medium

A. high should be initialized to n - 1, not n

B. low should start at 1, not 0

C. mid calculation should be (low - high) / 2

D. The loop condition should be low < high

Solution

1. Step 1: Check initialization of high pointer

   Array indices go from 0 to n-1, so high must be n-1, not n.

2. Step 2: Understand impact of wrong high value

   Setting high = n causes out-of-bounds access at arr[n], leading to undefined behavior.

3. Final Answer:

   high should be initialized to n - 1, not n -> Option A

4. Quick Check:

   Array index max is n-1, so high = n-1 [OK]

Hint: High index must be last valid index (n-1) [OK]

Common Mistakes:

• Setting high to n causing out-of-bounds
• Changing low start incorrectly
• Incorrect mid calculation formula

5. You have a sorted array of 10,000 elements. You want to find an element that is equally likely to be anywhere in the array. Which search method will have a lower average number of comparisons, and why?

hard

A. Both have the same average comparisons for random elements

B. Linear Search, because it checks elements sequentially

C. Binary Search, because it reduces search space by half each step

D. Linear Search, because it stops immediately when found

Solution

1. Step 1: Calculate average comparisons for Linear Search

   Linear Search checks on average half the array: 10,000 / 2 = 5,000 comparisons.

2. Step 2: Calculate average comparisons for Binary Search

   Binary Search takes about log2(10,000) ≈ 14 comparisons on average.

3. Step 3: Compare the two averages

   14 comparisons (Binary Search) is much less than 5,000 (Linear Search).

4. Final Answer:

   Binary Search, because it reduces search space by half each step -> Option C

5. Quick Check:

   Binary Search average comparisons << Linear Search [OK]

Hint: Binary Search average steps ~ log2(n), Linear ~ n/2 [OK]

Common Mistakes:

• Assuming Linear Search is faster because it stops early
• Ignoring that array must be sorted for Binary Search
• Confusing worst-case with average-case comparisons