Why Binary Search and What Sorted Order Gives You in DSA C# - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

What is the output of the following C# code that performs binary search on a sorted array?

DSA C#

using System;

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

    static void Main() {
        int[] sortedArr = {2, 4, 6, 8, 10, 12};
        int index = BinarySearch(sortedArr, 8);
        Console.WriteLine(index);
    }
}

A 3

B 2

C -1

D 4

💡 Hint

Remember that array indexing starts at 0 and binary search returns the index of the target if found.

The target 8 is at index 3 in the sorted array. Binary search finds it and returns 3.

🧠 Conceptual

intermediate

Why Must the Array Be Sorted for Binary Search?

Why is it necessary for the array to be sorted before performing binary search?

A Because binary search requires the array to be sorted in descending order only.

B Because binary search only works on arrays with unique elements.

C Because binary search can only find the first element in any array.

D Because binary search compares the target with the middle element and decides which half to search next, which only works if the array is sorted.

💡 Hint

Think about how binary search decides which half of the array to ignore.

Binary search relies on the order of elements to eliminate half the search space each time. Without sorting, this logic fails.

❓ Predict Output

advanced

Result of Binary Search on Unsorted Array

What will be the output of this C# code that runs binary search on an unsorted array?

DSA C#

using System;

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

    static void Main() {
        int[] unsortedArr = {2, 4, 10, 6, 12, 8};
        int index = BinarySearch(unsortedArr, 8);
        Console.WriteLine(index);
    }
}

A 3

B 2

C -1

D 4

💡 Hint

Binary search assumes the array is sorted. What happens if it is not?

Since the array is not sorted, binary search cannot reliably find the target and returns -1 indicating not found.

🔧 Debug

advanced

Find the Bug in Binary Search Implementation

What is the bug in this binary search code that causes it to fail for some inputs?

DSA C#

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;
}

A The calculation of 'mid' should be 'left + (right - left) / 2' to avoid overflow.

B The 'right' should be initialized to arr.Length - 1, not arr.Length.

C The loop condition should be 'left <= right' instead of 'left < right'.

D The function should return 'left' instead of '-1' when target is not found.

💡 Hint

Check the valid index range for the array.

Array indices go from 0 to Length - 1. Initializing 'right' to Length causes out-of-range access.

🧠 Conceptual

expert

Why Binary Search is More Efficient Than Linear Search on Sorted Data

Why is binary search generally faster than linear search when searching in sorted data?

A Because binary search reduces the search space by half each step, leading to logarithmic time complexity, while linear search checks elements one by one.

B Because linear search requires the array to be sorted, while binary search does not.

C Because binary search only works on small arrays, making it faster by default.

D Because binary search uses recursion, which is always faster than loops used in linear search.

💡 Hint

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

Binary search cuts the search space in half each time, so it runs in O(log n) time, much faster than linear search's O(n).

Practice

1. Why is it important for a list to be sorted before applying binary search?

easy

A. Because binary search can only find the first element in any list

B. Because binary search works only on lists with unique elements

C. Because binary search divides the list and compares values assuming order

D. Because binary search requires the list to be reversed

Solution

1. Step 1: Understand binary search working principle

   Binary search splits the list into halves and compares the middle element to the target, assuming the list is sorted.

2. Step 2: Importance of sorted order

   If the list is not sorted, the halves cannot be correctly chosen, so binary search fails to find the target efficiently.

3. Final Answer:

   Because binary search divides the list and compares values assuming order -> Option C

4. Quick Check:

   Sorted list needed for binary search = True [OK]

Hint: Binary search needs order to split search space correctly [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Assuming binary search finds duplicates only
• Confusing binary search with linear search

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

easy

A. int index = Array.BinarySearch(arr, target);

B. int index = arr.BinarySearch(target);

C. int index = BinarySearch(arr, target);

D. int index = arr.SearchBinary(target);

Solution

1. Step 1: Recall C# binary search method usage

   C# provides a static method Array.BinarySearch that takes the array and the target value.

2. Step 2: Check method call correctness

   int index = Array.BinarySearch(arr, target); correctly calls Array.BinarySearch(arr, target). Other options use invalid syntax or methods.

3. Final Answer:

   int index = Array.BinarySearch(arr, target); -> Option A

4. Quick Check:

   Correct C# binary search syntax = int index = Array.BinarySearch(arr, target); [OK]

Hint: Use Array.BinarySearch for arrays in C# [OK]

Common Mistakes:

• Trying to call BinarySearch as instance method on array
• Using wrong method names like SearchBinary
• Missing the Array class prefix

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

int[] arr = {2, 4, 6, 8, 10};
int index = Array.BinarySearch(arr, 6);
Console.WriteLine(index);

medium

A. -1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand array and target

   The array is sorted: [2, 4, 6, 8, 10]. The target is 6.

2. Step 2: Find index of target in array

   6 is at index 2 (0-based indexing).

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: BinarySearch returns index of found element [OK]

Common Mistakes:

• Confusing index with value
• Assuming 1-based indexing
• Expecting -1 when element is present

4. The following code tries to find the index of 5 in a sorted array but gives an unexpected result. What is the error?

int[] arr = {1, 3, 7, 9, 11};
int index = Array.BinarySearch(arr, 5);
Console.WriteLine(index);

medium

A. 5 is not in the array, so negative index is returned

B. The method call syntax is incorrect

C. BinarySearch cannot be used on integers

D. The array is not sorted

Solution

1. Step 1: Check if array is sorted

   The array [1, 3, 7, 9, 11] is sorted in ascending order.

2. Step 2: Understand BinarySearch return when element not found

   When the target (5) is not found, BinarySearch returns a negative number indicating the bitwise complement of the insertion point.

3. Final Answer:

   5 is not in the array, so negative index is returned -> Option A

4. Quick Check:

   Not found element returns negative index [OK]

Hint: Negative result means element not found [OK]

Common Mistakes:

• Thinking array is unsorted
• Expecting -1 always when not found
• Believing syntax is wrong

5. You have a sorted list of student scores: int[] scores = {55, 67, 78, 89, 92, 95}. You want to find if a score of 80 exists using binary search. If not found, you want to insert 80 in the correct position to keep the list sorted. Which approach correctly achieves this?

hard

A. Sort the array after inserting 80 at the end

B. Use Array.BinarySearch and insert at returned index directly

C. Use linear search to find 80 and insert if missing

D. Use Array.BinarySearch to find 80; if negative, insert at ~index returned

Solution

1. Step 1: Use Array.BinarySearch to find 80

   BinarySearch returns index if found; if not found, returns negative number which is bitwise complement of insertion point.

2. Step 2: Insert 80 at correct position

   If result is negative, invert bits (~index) to get insertion position to keep array sorted.

3. Final Answer:

   Use Array.BinarySearch to find 80; if negative, insert at ~index returned -> Option D

4. Quick Check:

   Negative index means insert at bitwise complement [OK]

Hint: Insert at ~index if BinarySearch returns negative [OK]

Common Mistakes:

• Inserting at negative index directly
• Not using binary search result properly
• Sorting after insertion instead of correct position