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 for a target value in an array.

DSA C++

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

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

Ai

Btarget

Cn

Darr

Attempts:

3 left

💡 Hint

Common Mistakes

Using the loop index instead of the target value in the comparison.

Comparing with the array name instead of an element.

The code checks if the current element arr[i] equals the target value we are searching for.

2fill in blank

medium

Complete the code to perform a binary search on a sorted array.

DSA C++

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

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

Amid

Bleft

Ctarget

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the wrong variable like left or right indices.

Using the middle index instead of the target value.

The binary search compares the middle element arr[mid] with the target value to decide the next search range.

3fill in blank

hard

Fix the error in the binary search condition to correctly update the search range.

DSA C++

if (arr[mid] < [1]) {
    left = mid + 1;
} else {
    right = mid - 1;
}

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

Atarget

Bleft

Cright

Dmid

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the left or right index instead of the target value.

Using the middle index instead of the target value.

The condition must compare arr[mid] with the target to decide which half to search next.

4fill in blank

hard

Fill both blanks to create a dictionary that maps each element to its index, then check if target exists.

DSA C++

std::unordered_map<int, int> indexMap;
for (int i = 0; i < n; i++) {
    indexMap[[1]] = i;
}
if (indexMap.find([2]) != indexMap.end()) {
    return indexMap[[2]];
} else {
    return -1;
}

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

Aarr[i]

Btarget

Ci

Darr

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index i as the key instead of the element.

Checking the map with the index instead of the target.

The first blank should be the element arr[i] to map it to its index. The second blank is the target to check if it exists in the map.

5fill in blank

hard

Fill all three blanks to create a map comprehension that stores elements greater than 10 with their squares.

DSA C++

std::unordered_map<int, int> result;
for (int [1] = 0; [1] < [3]; [1]++) {
    if (arr[[1]] [2] 10) {
        result[arr[[1]]] = arr[[1]] * arr[[1]];
    }
}

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

Ai

B>

C<

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong comparison operator like <.

Using the wrong loop variable or loop condition.

The loop variable is i. The condition checks if the element is greater than 10 using >. The loop runs while i < n.

Practice

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

easy

A. Binary Search

B. Linear Search

C. Both perform equally

D. Depends on the element position only

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 A

4. Quick Check:

   Binary Search is faster on sorted large arrays [OK]

Hint: Binary Search halves search space, so faster on sorted data [OK]

Common Mistakes:

• Thinking Linear Search is faster because it is simpler
• Ignoring that array must be sorted for Binary Search
• Assuming both have same speed regardless of data size

2. Which of the following is the correct syntax to start a binary search on a sorted array arr of size n in C++?

easy

A. int low = 0, high = n - 1;

B. int low = 1, high = n;

C. int low = 0, high = n;

D. int low = 1, high = n - 1;

Solution

1. Step 1: Understand array indexing in C++

   Arrays start at index 0, so first element is at 0 and last at n-1.

2. Step 2: Set binary search boundaries correctly

   Low should be 0 and high should be n-1 to cover entire array.

3. Final Answer:

   int low = 0, high = n - 1; -> Option A

4. Quick Check:

   Array indices start at 0, so low=0 and high=n-1 [OK]

Hint: Array indexing starts at 0, so high = n - 1 [OK]

Common Mistakes:

• Starting low at 1 instead of 0
• Setting high to n instead of n-1
• Confusing 1-based indexing with 0-based

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

int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int target = 6;
int low = 0, high = n - 1;
int steps = 0;
while (low <= high) {
    steps++;
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        break;
    } else if (arr[mid] < target) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
std::cout << steps << std::endl;

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace first iteration

   low=0, high=4, mid=2, arr[2]=6 equals target, steps=1, loop breaks immediately.

2. Step 2: Confirm steps count

   Steps incremented once before break, so output is 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Target found at first mid check, steps = 1 [OK]

Hint: Binary Search finds target quickly, count mid checks [OK]

Common Mistakes:

• Counting steps after break incorrectly
• Miscomputing mid index
• Assuming more iterations needed when target is mid

4. Identify the error in the following linear search code snippet and choose the correct fix:

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

medium

A. Change return i to return i + 1

B. Change loop to for (int i = 0; i < n; i++)

C. Change loop to for (int i = 1; i < n; i++)

D. No error, code is correct

Solution

1. Step 1: Analyze array indexing

   Arrays in C++ start at 0, but loop starts at 1 and goes to n, causing out-of-bounds access.

2. Step 2: Fix loop boundaries

   Loop should start at 0 and run while i < n to cover all elements safely.

3. Final Answer:

   Change loop to for (int i = 0; i < n; i++) -> Option B

4. Quick Check:

   Array indexing starts at 0, loop must reflect that [OK]

Hint: Array indices start at 0, loop from 0 to n-1 [OK]

Common Mistakes:

• Starting loop at 1 causing skip of first element
• Using <= n causing out-of-bounds access
• Assuming array indexing starts at 1

5. You have a sorted array of 1,000 elements and want to find if the number 500 exists. Which search method is more cost-effective considering average case and why?

hard

A. Linear Search, because it uses less memory

B. Linear Search, because it checks elements sequentially

C. Binary Search, because it reduces search space exponentially

D. Binary Search, but only if the array is unsorted

Solution

1. Step 1: Consider array sortedness and search methods

   Binary Search requires sorted array and halves search space each step; Linear Search checks each element one by one.

2. Step 2: Compare average case cost

   Binary Search takes about log2(1000) ≈ 10 steps; Linear Search takes on average 500 steps.

3. Final Answer:

   Binary Search, because it reduces search space exponentially -> Option C

4. Quick Check:

   Sorted array + binary search = faster average search [OK]

Hint: Use Binary Search on sorted arrays for faster average search [OK]

Common Mistakes:

• Choosing Linear Search for sorted arrays
• Confusing memory use with search speed
• Thinking Binary Search works on unsorted arrays