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 LinearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.Length; i++) {
        if (arr[i] == [1]) {
            return i;
        }
    }
    return -1;
}

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

Atarget

Bi

Carr

D0

Attempts:

3 left

💡 Hint

Common Mistakes

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

Comparing arr[i] to arr instead of target.

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

2fill in blank

medium

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

DSA C#

int BinarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.Length - 1;
    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'

Aleft

Btarget

Cmid

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing arr[mid] to left or right instead of target.

Using mid as the comparison value instead of arr[mid].

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

3fill in blank

hard

Fix the error in the binary search code: complete the condition to continue the loop correctly.

DSA C#

int BinarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.Length - 1;
    while (left [1] right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            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'

A<=

B<

C>=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' causes the loop to miss checking when left equals right.

Using '>' or '>=' reverses the logic and causes infinite loops.

The loop should continue while left is less than or equal to right to check all possible positions.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths only if length is greater than 3.

DSA C#

var result = new Dictionary<string, int>();
foreach (var word in words) {
    if (word.[1] > 3) {
        result[word] = word.[2];
    }
}

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

ALength

BCount

CLength()

DCount()

Attempts:

3 left

💡 Hint

Common Mistakes

Using Length() or Count() which are invalid for strings in C#.

Using Count property which is for collections, not strings.

In C#, string length is accessed by the Length property without parentheses.

5fill in blank

hard

Fill all three blanks to create a dictionary that maps uppercase words to their lengths only if length is greater than 4.

DSA C#

var result = new Dictionary<string, int>();
foreach (var word in words) {
    if (word.[1] > 4) {
        result[word.[2]()] = word.[3];
    }
}

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

ALength

BToUpper

DCount

Attempts:

3 left

💡 Hint

Common Mistakes

Using Count instead of Length for strings.

Using Length() with parentheses which is invalid.

Forgetting parentheses on ToUpper method.

Use Length property to check length, ToUpper() method to convert word, and Length property again for value.

Practice

1. Which search algorithm generally performs faster on a sorted list 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 list in half repeatedly, while Linear Search checks each element one by one.

2. Step 2: Compare performance on large sorted lists

   Binary Search runs in O(log n) time, which is much faster than Linear Search's O(n) time for large n.

3. Final Answer:

   Binary Search -> Option A

4. Quick Check:

   Binary Search faster on sorted large lists [OK]

Hint: Binary Search halves list each step, faster on sorted data [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted lists
• Ignoring the sorted list requirement for Binary Search
• Confusing average and worst-case times

2. Which of the following is the correct syntax to perform a linear search for value target in an integer array arr in C#?

easy

A. foreach (int i in arr) { if (i == target) return i; }

B. for (int i = 1; i <= arr.Length; i++) { if (arr[i] == target) return i; }

C. for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; }

D. while (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; }

Solution

1. Step 1: Check loop initialization and condition

   for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } correctly initializes i at 0 and loops while i is less than arr.Length, which is valid for array indexing.

2. Step 2: Verify element access and comparison

   for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } accesses arr[i] correctly and compares it to target, returning index if found.

3. Final Answer:

   for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } -> Option C

4. Quick Check:

   Correct for-loop syntax for linear search [OK]

Hint: Array indices start at 0; loop till less than length [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < in loop condition
• Incorrect loop syntax like while with initialization

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

int[] arr = {2, 4, 6, 8, 10};
int target = 6;
int index = -1;

// Linear Search
for (int i = 0; i < arr.Length; i++) {
    if (arr[i] == target) {
        index = i;
        break;
    }
}
Console.WriteLine(index);

medium

A. 2

B. 3

C. -1

D. 0

Solution

1. Step 1: Trace the loop to find target in array

   Array elements: 2(0), 4(1), 6(2), 8(3), 10(4). Loop checks each index until arr[i] == 6 at i=2.

2. Step 2: Assign index and break loop

   When found at i=2, index is set to 2 and loop breaks.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Index of target in array is position starting at 0 [OK]

Common Mistakes:

• Confusing value with index
• Off-by-one errors in indexing
• Not breaking loop after finding target

4. The following code attempts to perform a binary search on a sorted array but has a bug. What is the bug?

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

medium

A. Loop condition should be left < right

B. Array must be unsorted for binary search

C. Should return mid + 1 when found

D. Mid calculation can cause integer overflow

Solution

1. Step 1: Analyze mid calculation

   Mid is calculated as (left + right) / 2, which can overflow if left and right are large integers.

2. Step 2: Suggest safe mid calculation

   Use mid = left + (right - left) / 2 to avoid overflow.

3. Final Answer:

   Mid calculation can cause integer overflow -> Option D

4. Quick Check:

   Mid overflow risk in binary search [OK]

Hint: Use safe mid calculation to avoid overflow [OK]

Common Mistakes:

• Ignoring integer overflow in mid calculation
• Changing loop condition incorrectly
• Misunderstanding binary search requires sorted array

5. You have a sorted array of 1,000,000 integers and want to find if a number exists. You also know that the number is more likely to be near the start of the array. Which search method minimizes average search cost and why?

hard

A. Binary Search, because it always halves the search space

B. Linear Search, because it finds elements near the start faster

C. Binary Search, because it is faster for all positions

D. Linear Search, because it uses less memory

Solution

1. Step 1: Consider element distribution and search costs

   Binary Search takes O(log n) steps regardless of element position. Linear Search takes fewer steps if element is near start.

2. Step 2: Compare average costs given element likely near start

   Since element is likely near start, Linear Search will find it quickly on average, minimizing cost.

3. Final Answer:

   Linear Search, because it finds elements near the start faster -> Option B

4. Quick Check:

   Element near start favors Linear Search [OK]

Hint: Near start? Linear Search is faster on average [OK]

Common Mistakes:

• Assuming Binary Search always fastest
• Ignoring element distribution impact
• Confusing memory use with speed