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 an unsorted array?

DSA C#

int[] arr = {4, 2, 7, 1, 9};
int target = 7;
int index = -1;
for (int i = 0; i < arr.Length; i++)
{
    if (arr[i] == target)
    {
        index = i;
        break;
    }
}
Console.WriteLine(index);

A 2

B -1

C 0

D 3

💡 Hint

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

The linear search scans the array from start to end. The value 7 is at index 2, so the output is 2.

❓ Predict Output

intermediate

Output of Binary Search on a Sorted Array

What is the output of this C# code that performs a binary search for the value 5 in a sorted array?

DSA C#

int[] arr = {1, 3, 5, 7, 9};
int target = 5;
int left = 0, right = arr.Length - 1;
int index = -1;
while (left <= right)
{
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
    {
        index = mid;
        break;
    }
    else if (arr[mid] < target)
    {
        left = mid + 1;
    }
    else
    {
        right = mid - 1;
    }
}
Console.WriteLine(index);

A 1

B 3

C -1

D 2

💡 Hint

Binary search divides the array and looks at the middle element.

The target 5 is at index 2 in the sorted array, so the binary search finds it and prints 2.

🧠 Conceptual

advanced

Cost Difference Between Linear and Binary Search

Which statement best describes the real cost difference between linear search and binary search when searching for an element in a large sorted array?

A Binary search is always faster because it checks fewer elements by dividing the search space in half each time.

B Linear search is faster because it checks elements sequentially without extra calculations.

C Both searches have the same cost because they both look at elements one by one.

D Binary search is slower because it requires the array to be sorted first.

💡 Hint

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

Binary search reduces the search space by half each step, so it checks far fewer elements than linear search, which checks each element one by one.

❓ Predict Output

advanced

Output of Binary Search on an Unsorted Array

What is the output of this C# code that performs a binary search for the value 4 on an unsorted array?

DSA C#

int[] arr = {5, 3, 8, 4, 2};
int target = 4;
int left = 0, right = arr.Length - 1;
int index = -1;
while (left <= right)
{
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
    {
        index = mid;
        break;
    }
    else if (arr[mid] < target)
    {
        left = mid + 1;
    }
    else
    {
        right = mid - 1;
    }
}
Console.WriteLine(index);

A 3

B -1

C 2

D 0

💡 Hint

Binary search requires a sorted array to work correctly.

Because the array is unsorted, binary search does not find the target 4 and returns -1.

🧠 Conceptual

expert

When Linear Search Can Be More Efficient Than Binary Search

In which scenario can linear search be more efficient than binary search despite the array being sorted?

A When the array is sorted and the target is exactly in the middle.

B When the array is very large and the target is near the end.

C When the target element is near the beginning of a very large sorted array.

D When the array is unsorted and large.

💡 Hint

Consider the cost of binary search setup versus finding an element quickly at the start.

If the target is near the start, linear search finds it quickly without the overhead of binary search steps.

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