Binary Search Recursive Approach in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search Call

What is the output of the following C# code that uses recursive binary search to find the index of number 7 in the array?

DSA C#

using System;

class Program {
    static int BinarySearch(int[] arr, int left, int right, int target) {
        if (right < left) return -1;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) return BinarySearch(arr, left, mid - 1, target);
        else return BinarySearch(arr, mid + 1, right, target);
    }

    static void Main() {
        int[] numbers = {1, 3, 5, 7, 9, 11};
        int index = BinarySearch(numbers, 0, numbers.Length - 1, 7);
        Console.WriteLine(index);
    }
}

A -1

B 2

C 3

D 4

💡 Hint

Remember that array indexing starts at 0 and 7 is in the middle of the array.

The array is [1, 3, 5, 7, 9, 11]. The number 7 is at index 3 (0-based). The recursive binary search finds it and returns 3.

❓ Predict Output

intermediate

Result when target is not in array

What will be printed when searching for number 8 in the array using the recursive binary search below?

DSA C#

using System;

class Program {
    static int BinarySearch(int[] arr, int left, int right, int target) {
        if (right < left) return -1;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) return BinarySearch(arr, left, mid - 1, target);
        else return BinarySearch(arr, mid + 1, right, target);
    }

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

A -1

B 2

C 3

D 0

💡 Hint

If the target is not found, the function returns -1.

The number 8 is not in the array [2, 4, 6, 10, 12]. The binary search ends with no match and returns -1.

🔧 Debug

advanced

Identify the error in recursive binary search

What error will the following C# code produce when executed?

DSA C#

using System;

class Program {
    static int BinarySearch(int[] arr, int left, int right, int target) {
        if (left > right) return -1;
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) return BinarySearch(arr, mid + 1, right, target);
        else return BinarySearch(arr, left, mid - 1, target);
    }

    static void Main() {
        int[] numbers = {1, 2, 3, 4, 5};
        int index = BinarySearch(numbers, 0, numbers.Length - 1, 3);
        Console.WriteLine(index);
    }
}

A Compile-time error: missing return statement

B Prints 2

C StackOverflowException due to infinite recursion

D IndexOutOfRangeException at runtime

💡 Hint

Check the conditions for recursive calls and the order of comparisons.

The original code had the recursive calls swapped causing infinite recursion. This corrected version searches the right half when arr[mid] < target and left half otherwise, so it prints 2.

🧠 Conceptual

advanced

Number of recursive calls in worst case

For an array of size 64, what is the maximum number of recursive calls made by a recursive binary search in the worst case?

A 7

B 6

C 8

D 64

💡 Hint

Binary search divides the array size by 2 each call. Think about powers of 2.

Binary search halves the search space each call. For size 64, max calls = log2(64) + 1 = 6 + 1 = 7.

🚀 Application

expert

Find the missing number using recursive binary search

Given a sorted array of unique integers from 1 to 10 with one number missing, which recursive binary search call will find the missing number 6 by checking the mid element and comparing it to expected values? Assume the function returns the missing number or -1 if none missing.

DSA C#

int FindMissing(int[] arr, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] != mid + 1) {
        if (mid == 0 || arr[mid - 1] == mid) return mid + 1;
        else return FindMissing(arr, left, mid - 1);
    } else {
        return FindMissing(arr, mid + 1, right);
    }
}

int[] arr = {1, 2, 3, 4, 5, 7, 8, 9, 10};
int missing = FindMissing(arr, 0, arr.Length - 1);
Console.WriteLine(missing);

A 7

B -1

C 5

D 6

💡 Hint

The missing number is detected when the element does not match its expected value (index + 1).

The function finds the first index where arr[mid] != mid + 1. For the given array, this happens at index 5, so missing number is 6.

Practice

1. What is the main idea behind the Binary Search Recursive Approach when searching for a value in a sorted array?

easy

A. Use a queue to store elements and search iteratively.

B. Check every element one by one from start to end.

C. Sort the array first and then search linearly.

D. Divide the array into halves and search recursively in the half where the value can be.

Solution

1. Step 1: Understand binary search logic

   Binary search works by dividing the sorted array into two halves and deciding which half to search next based on the middle element.

2. Step 2: Recognize recursive approach

   The recursive approach calls the same search function on the half where the target value may exist, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the half where the value can be. -> Option D

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Remember: binary search splits array, searches half recursively [OK]

Common Mistakes:

• Thinking binary search checks every element linearly
• Not realizing array must be sorted first
• Confusing iterative and recursive approaches

2. Which of the following is the correct base case condition in a recursive binary search function in C#?

easy

A. if (array[start] == target) return start;

B. if (start == end) return start;

C. if (start > end) return -1;

D. if (end < start) return 0;

Solution

1. Step 1: Identify base case meaning

   The base case stops recursion when the search space is invalid, meaning start index is greater than end index.

2. Step 2: Match condition to code

   The condition if (start > end) return -1; correctly indicates the target is not found.

3. Final Answer:

   if (start > end) return -1; -> Option C

4. Quick Check:

   Base case = invalid range returns -1 [OK]

Hint: Base case: start index passes end index means not found [OK]

Common Mistakes:

• Using wrong comparison like start == end as base case
• Returning 0 which can be a valid index
• Not handling base case causing infinite recursion

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

int[] arr = {2, 4, 6, 8, 10};
int result = BinarySearch(arr, 0, arr.Length - 1, 6);
Console.WriteLine(result);

int BinarySearch(int[] array, int start, int end, int target) {
    if (start > end) return -1;
    int mid = (start + end) / 2;
    if (array[mid] == target) return mid;
    else if (array[mid] > target) return BinarySearch(array, start, mid - 1, target);
    else return BinarySearch(array, mid + 1, end, target);
}

medium

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Trace initial call and mid calculation

   Initial call: start=0, end=4, mid=(0+4)/2=2. array[2]=6 matches target 6.

2. Step 2: Return mid index

   Since array[mid] == target, function returns 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check mid index first; if match, return immediately [OK]

Common Mistakes:

• Miscomputing mid index
• Returning wrong index due to off-by-one errors
• Confusing array values with indices

4. Identify the error in this recursive binary search function and choose the correct fix:

int BinarySearch(int[] array, int start, int end, int target) {
    if (start >= end) return -1;
    int mid = (start + end) / 2;
    if (array[mid] == target) return mid;
    else if (array[mid] > target) return BinarySearch(array, start, mid - 1, target);
    else return BinarySearch(array, mid + 1, end, target);
}

medium

A. Change mid calculation to mid = (start + end + 1) / 2;

B. Change base case to if (start > end) return -1;

C. Return 0 instead of -1 in base case.

D. Remove the base case entirely.

Solution

1. Step 1: Analyze base case condition

   The base case uses start >= end, which wrongly excludes the case when start == end, missing the last element check.

2. Step 2: Correct base case to allow checking when start == end

   Changing to start > end ensures the last element is checked before stopping recursion.

3. Final Answer:

   Change base case to if (start > end) return -1; -> Option B

4. Quick Check:

   Base case must allow start == end check [OK]

Hint: Base case should be start > end, not start >= end [OK]

Common Mistakes:

• Stopping recursion too early with wrong base case
• Changing mid calculation unnecessarily
• Returning 0 which can be a valid index

5. Given a sorted array with possible duplicate values, how can you modify the recursive binary search to find the first occurrence of a target value?

hard

A. When array[mid] == target, continue searching left half to find earlier occurrence.

B. Return mid immediately when array[mid] == target.

C. Search right half only when array[mid] == target.

D. Use linear search after binary search to find first occurrence.

Solution

1. Step 1: Understand duplicates and first occurrence

   Duplicates mean target can appear multiple times; to find first occurrence, we must check if earlier indices also have the target.

2. Step 2: Modify recursion to search left half when target found

   When array[mid] == target, recursively search left half to find if target appears earlier; if none found, return current mid.

3. Final Answer:

   When array[mid] == target, continue searching left half to find earlier occurrence. -> Option A

4. Quick Check:

   Find first occurrence by searching left half on match [OK]

Hint: On match, search left half to find first occurrence [OK]

Common Mistakes:

• Returning first found index without checking left side
• Searching right half on match which finds last occurrence
• Using linear search after binary search unnecessarily