Binary Search as Divide and Conquer in DSA C# - Practice Problems & Challenges

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 to find the index of the number 7?

DSA C#

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

int[] numbers = {1, 3, 5, 7, 9, 11};
int result = BinarySearch(numbers, 7);
System.Console.WriteLine(result);

A 4

B 2

C -1

D 3

💡 Hint

Remember array indexing starts at 0. Binary search returns the index where the target is found.

The number 7 is at index 3 in the array. The binary search finds it and returns 3.

❓ Predict Output

intermediate

Binary Search Result When Target Not Present

What will be printed when the binary search function is called with target 8 on the sorted array below?

DSA C#

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

int[] numbers = {2, 4, 6, 10, 12};
int result = BinarySearch(numbers, 8);
System.Console.WriteLine(result);

A -1

B 2

C 3

D 0

💡 Hint

If the target is not found, binary search returns -1.

The number 8 is not in the array, so the function returns -1.

🧠 Conceptual

advanced

Divide and Conquer Principle in Binary Search

Which statement best describes how binary search uses the divide and conquer approach?

A It divides the array into two halves and recursively searches only the half that may contain the target.

B It searches both halves of the array simultaneously to find the target faster.

C It divides the array into multiple parts and searches all parts in parallel.

D It sorts the array first and then performs a linear search on the entire array.

💡 Hint

Think about how binary search reduces the search space each step.

Binary search splits the array into two halves and continues searching only the half where the target could be, ignoring the other half.

🔧 Debug

advanced

Identify the Bug in Binary Search Implementation

What error will occur when running this binary search code?

DSA C#

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

int[] numbers = {1, 2, 3, 4, 5};
int result = BinarySearch(numbers, 6);
System.Console.WriteLine(result);

A Infinite loop

B Returns -1 even if target is present

C IndexOutOfRangeException

D No error, prints -1

💡 Hint

Check the value of 'right' and how it is used to access array elements.

The variable 'right' is set to arr.Length, which is out of valid index range (max index is Length-1). Accessing arr[mid] when mid equals Length causes IndexOutOfRangeException.

🚀 Application

expert

Binary Search to Find First Occurrence in Sorted Array with Duplicates

Given a sorted array with duplicates, which code snippet correctly finds the first index of the target using binary search?

A

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

B

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

C

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;

D

int left = 0, right = arr.Length;
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;

💡 Hint

To find the first occurrence, update result and continue searching left half.

Option B updates 'result' when target is found and moves 'right' to mid-1 to find earlier occurrences. This ensures the first index is found.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It repeatedly divides the search interval in half to find the target value.

B. It checks every element one by one until it finds the target.

C. It sorts the array before searching for the target.

D. It uses a queue to store elements during the search.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the array into two halves and decides which half to search next.

2. Step 2: Identify the repeated halving process

   It keeps dividing the search space by half until the target is found or no elements remain.

3. Final Answer:

   It repeatedly divides the search interval in half to find the target value. -> Option A

4. Quick Check:

   Divide and conquer = repeated halving [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Thinking binary search checks every element
• Confusing binary search with linear search
• Assuming binary search sorts the array

2. Which of the following is the correct C# syntax to calculate the middle index in binary search to avoid overflow?

easy

A. int mid = (low + high) / 2;

B. int mid = (low - high) / 2;

C. int mid = low + (high - low) / 2;

D. int mid = (low * high) / 2;

Solution

1. Step 1: Understand overflow risk in mid calculation

   Adding low and high directly can overflow if both are large.

2. Step 2: Use safe formula to avoid overflow

   Calculating mid as low + (high - low) / 2 prevents overflow by subtracting first.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option C

4. Quick Check:

   Safe mid calculation = low + (high - low) / 2 [OK]

Hint: Use low + (high - low) / 2 to avoid overflow [OK]

Common Mistakes:

• Using (low + high) / 2 causing overflow
• Subtracting incorrectly in mid calculation
• Multiplying indices instead of adding

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

int[] arr = {2, 4, 6, 8, 10};
int target = 6;
int low = 0, high = arr.Length - 1;
int result = -1;
while (low <= high) {
  int mid = low + (high - low) / 2;
  if (arr[mid] == target) {
    result = mid;
    break;
  } else if (arr[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}
Console.WriteLine(result);

medium

A. 3

B. 2

C. -1

D. 0

Solution

1. Step 1: Trace the binary search steps

   Initial low=0, high=4, mid=2 (element 6). arr[2] == target 6, so result=2 and loop breaks.

2. Step 2: Output the result

   Since target found at index 2, Console.WriteLine prints 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value first to find target quickly [OK]

Common Mistakes:

• Confusing index with value
• Not updating low and high correctly
• Assuming target not found and returning -1

4. Identify the bug in this binary search code snippet and select the correct fix:

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

medium

A. Return 'low' instead of '-1' when target not found.

B. Change mid calculation to '(low + high) / 2' to simplify.

C. Remove 'else' before 'high = mid - 1;' to fix logic.

D. Change while condition to 'low <= high' to include last element.

Solution

1. Step 1: Analyze the loop condition

   The condition 'low < high' misses checking when low equals high, possibly skipping last element.

2. Step 2: Fix loop to include all elements

   Changing condition to 'low <= high' ensures the last element is checked.

3. Final Answer:

   Change while condition to 'low <= high' to include last element. -> Option D

4. Quick Check:

   Loop condition must cover all indices [OK]

Hint: Use 'low <= high' to cover full search range [OK]

Common Mistakes:

• Using 'low < high' and missing last element
• Changing mid calculation unnecessarily
• Returning wrong index when not found

5. You have a sorted array with duplicate values: int[] arr = {1, 2, 2, 2, 3, 4}. How would you modify binary search to find the first occurrence of 2?

hard

A. After finding target, continue searching left half to find first occurrence.

B. Return the first found index immediately without further checks.

C. Search the right half after finding target to find last occurrence.

D. Use linear search instead of binary search for duplicates.

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any occurrence, not necessarily the first.

2. Step 2: Modify search to find first occurrence

   When target found, move high pointer to mid - 1 to check left side for earlier occurrence, keep track of current mid.

3. Final Answer:

   After finding target, continue searching left half to find first occurrence. -> Option A

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: Keep searching left half after finding target for first occurrence [OK]

Common Mistakes:

• Stopping at first found index ignoring duplicates
• Searching right half instead of left for first occurrence
• Using linear search unnecessarily