Binary Search Recursive Approach in DSA C++

Mental Model

Binary search splits a sorted list in half repeatedly to find a target quickly by checking the middle element each time.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding to look in the left or right half depending on the word you see.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:     [0, 1, 2, 3, 4,  5,  6]
Search range: ↑                 ↑
Middle:           ↑

Dry Run Walkthrough

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

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

Step 1: Check middle element at index 3 (value 7)

[1, 3, 5, 7, 9, 11, 13]
search range indices: 0 to 6
middle index: 3 (value 7)

Why: We start by checking the middle to decide which half to search next

Step 2: Target 9 is greater than 7, search right half from index 4 to 6

[1, 3, 5, 7, 9, 11, 13]
search range indices: 4 to 6
middle index: 5 (value 11)

Why: Since 9 > 7, the target must be in the right half

Step 3: Target 9 is less than 11, search left half from index 4 to 4

[1, 3, 5, 7, 9, 11, 13]
search range indices: 4 to 4
middle index: 4 (value 9)

Why: Since 9 < 11, the target must be in the left half of current range

Step 4: Middle element 9 equals target, return index 4

[1, 3, 5, 7, 9, 11, 13]
found target at index 4

Why: We found the target, so we return its index

Result:

Final state: [1, 3, 5, 7, 9, 11, 13]
Target 9 found at index 4

Annotated Code

DSA C++

#include <iostream>
#include <vector>

int binarySearchRecursive(const std::vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1; // target not found
    }
    int mid = left + (right - left) / 2; // find middle index
    if (arr[mid] == target) {
        return mid; // target found
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right); // search right half
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1); // search left half
    }
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 9;
    int index = binarySearchRecursive(arr, target, 0, arr.size() - 1);
    if (index != -1) {
        std::cout << "Target " << target << " found at index " << index << "\n";
    } else {
        std::cout << "Target " << target << " not found in the array\n";
    }
    return 0;
}

if (left > right) { return -1; }

stop recursion if search range is invalid (target not found)

int mid = left + (right - left) / 2;

calculate middle index to split search range

if (arr[mid] == target) { return mid; }

check if middle element is the target

else if (arr[mid] < target) { return binarySearchRecursive(arr, target, mid + 1, right); }

search right half if target is greater than middle

else { return binarySearchRecursive(arr, target, left, mid - 1); }

search left half if target is less than middle

Output

Target 9 found at index 4

Complexity Analysis

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

Space: O(log n) due to recursive 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 left > right

DSA C++

if (left > right) { return -1; }

target not in array

recursion ends when left > right and returns -1

DSA C++

if (left > right) { return -1; }

single element array with target present

returns index 0 if element matches target

DSA C++

if (arr[mid] == target) { return mid; }

When to Use This Pattern

When you need to find an item quickly in a sorted list, use recursive binary search because it efficiently halves the search space each step.

Common Mistakes

Mistake: Calculating middle index as (left + right) / 2 without handling overflow
Fix: Calculate middle as left + (right - left) / 2 to avoid integer overflow

Mistake: Not updating left or right correctly in recursive calls
Fix: Ensure recursive calls use mid + 1 or mid - 1 to shrink search range properly

Summary

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

Use it when you have a sorted list and want to find an element quickly.

The key insight is that each step halves the search space, making the search very fast.