C# Program for Binary Search Using Recursion

A C# program for binary search using recursion calls a method that checks the middle element and recursively searches the left or right half using if (target == arr[mid]) return mid; and recursive calls like BinarySearch(arr, left, mid - 1, target) or BinarySearch(arr, mid + 1, right, target).

Examples

Inputarr = {1, 3, 5, 7, 9}, target = 7

Output3

Inputarr = {2, 4, 6, 8, 10}, target = 2

Output0

Inputarr = {1, 2, 3, 4, 5}, target = 10

Output-1

How to Think About It

To do a binary search with recursion, you start by looking at the middle of the sorted list. If the middle value is the one you want, you return its position. If the target is smaller, you search the left half; if bigger, the right half. You keep doing this until you find the target or the search space is empty.

Algorithm

1

Start with the full array and find the middle index.

2

Compare the middle element with the target value.

3

If they are equal, return the middle index.

4

If the target is less, recursively search the left half.

5

If the target is greater, recursively search the right half.

6

If the search space is empty, return -1 to indicate not found.

Code

csharp

using System;
class Program {
    static int BinarySearch(int[] arr, int left, int right, int target) {
        if (left > right) 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[] arr = {1, 3, 5, 7, 9};
        int target = 7;
        int result = BinarySearch(arr, 0, arr.Length - 1, target);
        Console.WriteLine(result);
    }
}

Output

3

Dry Run

Let's trace searching for 7 in the array {1, 3, 5, 7, 9} using recursion.

1

Initial call

left=0, right=4, mid=2, arr[mid]=5, target=7

2

Target greater than mid element

Search right half: left=3, right=4

3

Second call

left=3, right=4, mid=3, arr[mid]=7, target=7

4

Target found

Return index 3

Call	Left	Right	Mid	arr[Mid]	Target	Action
1	0	4	2	5	7	Search right half
2	3	4	3	7	7	Found target

Why This Works

Step 1: Check middle element

The code calculates the middle index and compares the middle element with the target using arr[mid] == target.

Step 2: Decide search half

If the target is smaller than the middle element, it searches the left half by calling itself with right = mid - 1.

Step 3: Recursive search

If the target is larger, it searches the right half with left = mid + 1. This repeats until the target is found or the search space is empty.

Alternative Approaches

Iterative binary search

csharp

using System;
class Program {
    static int BinarySearchIterative(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[] arr = {1, 3, 5, 7, 9};
        int target = 7;
        Console.WriteLine(BinarySearchIterative(arr, target));
    }
}

This avoids recursion and uses a loop, which can be more memory efficient for large arrays.

Using Array.BinarySearch method

csharp

using System;
class Program {
    static void Main() {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 7;
        int index = Array.BinarySearch(arr, target);
        Console.WriteLine(index >= 0 ? index : -1);
    }
}

This uses the built-in .NET method which is optimized and simple but does not show recursion.

Complexity: O(log n) time, O(log n) space

Time Complexity

Binary search divides the search space in half each time, so it runs in logarithmic time, O(log n).

Space Complexity

Recursive calls add to the call stack, so space complexity is O(log n) due to recursion depth.

Which Approach is Fastest?

Iterative binary search uses O(1) space and is faster in practice due to no recursion overhead, but recursive is easier to understand.

Approach	Time	Space	Best For
Recursive Binary Search	O(log n)	O(log n)	Learning recursion and divide-and-conquer
Iterative Binary Search	O(log n)	O(1)	Performance-critical applications
Array.BinarySearch Method	O(log n)	O(1)	Quick, built-in solution