Binary Search vs Linear Search Real Cost Difference in DSA C - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linear Search on an Unsorted Array

What is the output of the following C code that performs a linear search for the value 7 in the array?

DSA C

int arr[] = {3, 5, 7, 9, 11};
int n = 5;
int target = 7;
int i;
int found_index = -1;
for(i = 0; i < n; i++) {
    if(arr[i] == target) {
        found_index = i;
        break;
    }
}
printf("%d\n", found_index);

A -1

B 2

C 0

D 3

💡 Hint

Linear search checks each element until it finds the target or reaches the end.

The linear search finds the target 7 at index 2 in the array and prints 2.

❓ Predict Output

intermediate

Output of Binary Search on a Sorted Array

What is the output of the following C code that performs a binary search for the value 7 in the sorted array?

DSA C

int arr[] = {1, 3, 5, 7, 9, 11};
int n = 6;
int target = 7;
int left = 0, right = n - 1, mid;
int found_index = -1;
while(left <= right) {
    mid = left + (right - left) / 2;
    if(arr[mid] == target) {
        found_index = mid;
        break;
    } else if(arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
printf("%d\n", found_index);

A 3

B 2

C -1

D 4

💡 Hint

Binary search divides the search space in half each step.

The binary search finds the target 7 at index 3 and prints 3.

🧠 Conceptual

advanced

Comparing Time Complexity of Linear and Binary Search

Which statement correctly compares the time complexity of linear search and binary search on an array of size n?

A Both linear and binary search take O(n) time regardless of array sorting.

B Linear search takes O(log n) time; binary search takes O(n) time and works on unsorted arrays.

C Linear search takes O(n) time; binary search takes O(log n) time but requires a sorted array.

D Binary search takes O(n^2) time; linear search takes O(log n) time on sorted arrays.

💡 Hint

Think about how many elements each search checks in the worst case.

Linear search checks each element one by one, so O(n). Binary search divides the search space in half each step, so O(log n), but only works on sorted arrays.

❓ Predict Output

advanced

Output of Binary Search on an Unsorted Array

What is the output of the following C code that performs a binary search for the value 7 on an unsorted array?

DSA C

int arr[] = {9, 3, 7, 1, 11};
int n = 5;
int target = 7;
int left = 0, right = n - 1, mid;
int found_index = -1;
while(left <= right) {
    mid = left + (right - left) / 2;
    if(arr[mid] == target) {
        found_index = mid;
        break;
    } else if(arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
printf("%d\n", found_index);

A -1

B 0

C 3

D 2

💡 Hint

Binary search requires sorted arrays to work correctly.

Even though the array is unsorted, the first mid calculation lands on index 2 where arr[2] == 7, so it finds and prints 2. Binary search is not guaranteed to work on unsorted arrays.

🧠 Conceptual

expert

Real Cost Difference Between Linear and Binary Search

Which of the following best describes the real cost difference between linear search and binary search when searching for an element in a large dataset?

A Linear search can be faster on small or unsorted datasets, while binary search is faster on large, sorted datasets due to fewer comparisons.

B Both searches have the same cost in practice because modern CPUs optimize linear search heavily.

C Linear search uses less memory and is faster on sorted arrays, while binary search requires extra memory and is slower.

D Binary search is always faster because it uses fewer comparisons regardless of data structure or sorting.

💡 Hint

Consider dataset size and whether the data is sorted.

Binary search requires sorted data and fewer comparisons, making it faster on large sorted datasets. Linear search is simpler and can be faster on small or unsorted data.

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