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.

Practice

1. What is the main idea behind the binary search recursive approach?

easy

A. Use recursion to reverse the array before searching

B. Divide the array into halves and search recursively in the relevant half

C. Sort the array recursively before searching

D. Search every element one by one recursively

Solution

1. Step 1: Understand binary search logic

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

2. Step 2: Apply recursion in binary search

   Recursion calls the same function on the half where the target might be, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the relevant half -> Option B

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Think divide and conquer, search half each time [OK]

Common Mistakes:

• Searching all elements recursively instead of half
• Sorting inside the search function
• Not reducing search space correctly

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

easy

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

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

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

D. if (start == 0) return 0;

Solution

1. Step 1: Identify when search should stop

   The search should stop when the start index is greater than the end index, meaning the element is not found.

2. Step 2: Confirm base case condition

   Checking if start > end returns -1 to indicate the target is missing.

3. Final Answer:

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

4. Quick Check:

   Base case = start > end means not found [OK]

Hint: Stop when start passes end, return -1 [OK]

Common Mistakes:

• Using start == end as base case incorrectly
• Returning wrong index when not found
• Confusing start and end conditions

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

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

int main() {
  int arr[] = {2, 4, 6, 8, 10};
  int index = binarySearch(arr, 0, 4, 6);
  std::cout << index;
  return 0;
}

medium

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Identify the target and array

   The array is {2,4,6,8,10} and target is 6.

2. Step 2: Trace recursive calls

   First mid = 2 (index 2), arr[2] = 6 matches target, so return 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check middle element first, return index if match [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Not returning correct index

4. Find the error in this recursive binary search function:

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

medium

A. Mid calculation should be start - end instead of start + end

B. Return value should be target, not index

C. Base case condition should be start > end, not start >= end

D. Recursive calls should swap start and end

Solution

1. Step 1: Analyze base case condition

   The base case incorrectly uses start >= end, which misses checking when start == end.

2. Step 2: Correct base case for full search

   It should be start > end to allow checking the last element at start == end.

3. Final Answer:

   Base case condition should be start > end, not start >= end -> Option C

4. Quick Check:

   Base case = start > end to stop [OK]

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

Common Mistakes:

• Using >= instead of > in base case
• Wrong mid calculation formula
• Returning wrong values

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

hard

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

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

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

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

Solution

1. Step 1: Understand duplicates in sorted array

   Duplicates mean target can appear multiple times; we want the first index.

2. Step 2: Modify recursive search on match

   When arr[mid] == target, recursively search left half to check for earlier occurrence, else return mid.

3. Step 3: Implement logic

   If left recursive call returns valid index, return it; otherwise return mid.

4. Final Answer:

   When arr[mid] == target, continue searching left half to find earlier occurrence -> Option D

5. Quick Check:

   Find first occurrence = search left 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
• Using linear search unnecessarily