Binary Search vs Linear Search Real Cost Difference in DSA C - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a linear search that returns the index of the target or -1 if not found.

DSA C

int linear_search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == [1]) {
            return i;
        }
    }
    return -1;
}

Drag options to blanks, or click blank then click option'

Atarget

Bsize

Ci

Darr

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing arr[i] with size or i instead of target.

Returning the wrong index or value.

The code compares each element arr[i] with the target value to find a match.

2fill in blank

medium

Complete the code to calculate the middle index for binary search.

DSA C

int mid = [1] + (high - low) / 2;

Drag options to blanks, or click blank then click option'

Asize

Bhigh

C0

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Using high alone or zero instead of low in the calculation.

Calculating mid incorrectly causing infinite loops.

The middle index is calculated by adding low to half the distance between high and low.

3fill in blank

hard

Fix the error in the binary search condition to check if the target is less than the middle element.

DSA C

if (target [1] arr[mid]) {
    high = mid - 1;
} else if (target > arr[mid]) {
    low = mid + 1;
} else {
    return mid;
}

Drag options to blanks, or click blank then click option'

A>

B!=

C<

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' causing wrong search direction.

Using equality or inequality operators incorrectly.

To move the search to the left half, check if target is less than arr[mid].

4fill in blank

hard

Fill both blanks to create a loop that runs while low is less than or equal to high.

DSA C

while ([1] <= [2]) {
    int mid = low + (high - low) / 2;
    // binary search steps
}

Drag options to blanks, or click blank then click option'

Alow

Bhigh

Csize

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Using size or target instead of high in the condition.

Using incorrect comparison operators.

The loop continues while low index is less than or equal to high index.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension-like structure in C style pseudocode for counting elements greater than zero.

DSA C

for (int [1] = 0; [1] < size; [1]++) {
    if (arr[[3]] [2] 0) {
        count++;
    }
}

Drag options to blanks, or click blank then click option'

Ai

B>

C<

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for loop and indexing.

Using '<' instead of '>' causing wrong condition.

Use 'i' as loop variable, check if arr[i] > 0, and use 'i' again for indexing.

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