Coding Exercise: Binary Search Using Recursion

Find target in sorted array using divide-and-conquer: [1,3,5,7,9] target=5 → index 2.

Each step: mid check → left/right half → repeat.

Problem Statement

Input: Sorted array arr, target value

Output: Index of target or -1 if not found

Examples: [1,3,5,7], 5 → 2; [1,3,5,7], 4 → -1

Approach: Divide & Conquer

1. Base: left > right → -1 (not found)

2. mid = (left+right)/2

3. arr[mid] == target → return mid

4. arr[mid] > target → search left half

5. arr[mid] < target → search right half

Solution Code

              
            
C++

          Recursive binary search
        
#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
    // Base case: not found
    if (left > right) return -1;
    
    // Mid point
    int mid = left + (right - left) / 2;
    
    // Found
    if (arr[mid] == target) return mid;
    
    // Search left half
    if (arr[mid] > target)
        return binarySearch(arr, left, mid-1, target);
    
    // Search right half
    return binarySearch(arr, mid+1, right, target);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = 5;
    int target = 5;
    
    int result = binarySearch(arr, 0, n-1, target);
    if (result != -1)
        cout << "Found at index " << result << endl;
    else
        cout << "Not found" << endl;
    return 0;
}

Dry Run: [2,4,6,8,10,12], target=8

              
TEXT

          Step-by-step search
        
Step 1: [2,4,6,8,10,12] left=0,right=5, mid=2 → 6<8 → right half
Step 2: [8,10,12]     left=3,right=5, mid=4 → 10>8 → left half
Step 3: [8,10]        left=3,right=4, mid=3 → 8==8 → FOUND index 3 ✓

Test Cases

              
            
TEXT

          Expected outputs
        
[1,3,5], 3 → 1
[1,3,5], 4 → -1
[1], 1 → 0
[], 1 → -1

Complexity Analysis

Time: O(log n) - halves search space

Space: O(log n) - recursion depth

Practice Variations

1. Find first/last occurrence

2. Binary search on rotated array

3. Count occurrences using binary search

Conclusion

Mastered recursive binary search! O(log n) divide-conquer.

Next: Merge sort or quicksort recursively.