Binary Search Recursive Approach in DSA C#

Mental Model

Binary search splits a sorted list in half to find a target quickly by checking the middle element and searching only the half that could contain the target.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if you should look in the first half or the second half, and repeating this until you find the word.

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
                 ↑mid
Search range: low=0, high=9

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target: 13

Goal: Find the index of target 13 using recursive binary search

Step 1: Calculate mid index between low=0 and high=9, mid=4, check value 9

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Search range: low=0, high=9, mid=4 (value=9)

Why: We check middle to decide which half to search next

Step 2: Since 13 > 9, search right half: low=5, high=9

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Search range: low=5, high=9

Why: Target is greater than mid value, so discard left half

Step 3: Calculate mid index between low=5 and high=9, mid=7, check value 15

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Search range: low=5, high=9, mid=7 (value=15)

Why: Check middle of new search range

Step 4: Since 13 < 15, search left half: low=5, high=6

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Search range: low=5, high=6

Why: Target is less than mid value, so discard right half

Step 5: Calculate mid index between low=5 and high=6, mid=5, check value 11

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Search range: low=5, high=6, mid=5 (value=11)

Why: Check middle of new search range

Step 6: Since 13 > 11, search right half: low=6, high=6

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Search range: low=6, high=6

Why: Target is greater than mid value, so discard left half

Step 7: Calculate mid index between low=6 and high=6, mid=6, check value 13

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Search range: low=6, high=6, mid=6 (value=13)

Why: Check middle of new search range

Step 8: Found target 13 at index 6, return 6

Final result: index 6

Why: Target matches mid value, search ends

Result:

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> [17] -> [19]
Indexes:  0      1      2      3      4       5       6       7       8       9
Target 13 found at index 6

Annotated Code

DSA C#

using System;

class BinarySearchRecursive
{
    public static int BinarySearch(int[] arr, int target, int low, int high)
    {
        if (low > high) // base case: target not found
            return -1;

        int mid = low + (high - low) / 2; // find middle index

        if (arr[mid] == target) // target found
            return mid;
        else if (arr[mid] > target) // search left half
            return BinarySearch(arr, target, low, mid - 1);
        else // search right half
            return BinarySearch(arr, target, mid + 1, high);
    }

    static void Main()
    {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 13;
        int index = BinarySearch(arr, target, 0, arr.Length - 1);
        if (index != -1)
            Console.WriteLine($"Target {target} found at index {index}");
        else
            Console.WriteLine($"Target {target} not found");
    }
}

if (low > high) // base case: target not found

stop recursion when search range is invalid

int mid = low + (high - low) / 2; // find middle index

calculate middle index of current search range

if (arr[mid] == target) // target found

check if middle element is the target

else if (arr[mid] > target) // search left half

if target is smaller, recurse left half

else // search right half

if target is larger, recurse right half

Output

Target 13 found at index 6

Complexity Analysis

Time: O(log n) because each recursive call halves the search range

Space: O(log n) due to recursion call stack depth proportional to log n

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by reducing search space quickly

Edge Cases

empty array

returns -1 immediately as low > high

DSA C#

if (low > high) // base case: target not found

target not in array

recursion ends when low > high, returns -1

DSA C#

if (low > high) // base case: target not found

single element array with target present

returns index 0 immediately if arr[0] == target

DSA C#

if (arr[mid] == target) // target found

single element array with target absent

returns -1 after checking single element

DSA C#

if (low > high) // base case: target not found

When to Use This Pattern

When you see a problem asking to find an element in a sorted list quickly, reach for binary search recursive approach because it efficiently halves the search space each step.

Common Mistakes

Mistake: Not updating low and high correctly in recursive calls causing infinite recursion
Fix: Ensure recursive calls use mid - 1 or mid + 1 to shrink search range properly

Mistake: Calculating mid as (low + high) / 2 without handling integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Forgetting base case when low > high leading to stack overflow
Fix: Add base case to return -1 when low > high

Summary

It finds a target value in a sorted array by recursively checking the middle and searching half the array.

Use it when you need fast search in sorted data.

The key insight is cutting the search space in half each step to quickly zero in on the target.

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