Binary Search Recursive Approach in DSA C

Mental Model

Binary search splits a sorted list in half to find a value quickly by checking the middle and deciding which half to search next.

Analogy: Like guessing a number between 1 and 100 by asking if it is higher or lower than the middle number, then narrowing down the range each time.

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Indexes:  0      1      2      3      4       5       6
Search range: low -> mid -> high

Dry Run Walkthrough

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

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

Step 1: Calculate mid index between low=0 and high=6, mid=3; compare array[mid]=7 with 9

[1, 3, 5, 7, 9, 11, 13]
Indexes: 0  1  2  3  4  5  6
low=0, mid=3, high=6

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

Step 2: Since 7 < 9, search right half: low=mid+1=4, high=6

[1, 3, 5, 7, 9, 11, 13]
Indexes: 0  1  2  3  4  5  6
low=4, high=6

Why: Value must be in right half because 9 is greater than middle

Step 3: Calculate mid between low=4 and high=6, mid=5; compare array[mid]=11 with 9

[1, 3, 5, 7, 9, 11, 13]
Indexes: 0  1  2  3  4  5  6
low=4, mid=5, high=6

Why: Check middle of new range to narrow search

Step 4: Since 11 > 9, search left half: low=4, high=mid-1=4

[1, 3, 5, 7, 9, 11, 13]
Indexes: 0  1  2  3  4  5  6
low=4, high=4

Why: Value must be in left half because 9 is less than middle

Step 5: Calculate mid between low=4 and high=4, mid=4; compare array[mid]=9 with 9

[1, 3, 5, 7, 9, 11, 13]
Indexes: 0  1  2  3  4  5  6
low=4, mid=4, high=4

Why: Check middle of final range

Step 6: Found value at index 4; return index 4

[1, 3, 5, 7, 9, 11, 13]
Indexes: 0  1  2  3  4  5  6
Found at index 4

Why: Value matches array[mid], search ends

Result:

[1, 3, 5, 7, 9, 11, 13]
Found value 9 at index 4

Annotated Code

DSA C

#include <stdio.h>

int binary_search_recursive(int arr[], int low, int high, int target) {
    if (low > high) {
        return -1; // base case: not found
    }
    int mid = low + (high - low) / 2; // find middle index
    if (arr[mid] == target) {
        return mid; // found target
    } else if (arr[mid] < target) {
        return binary_search_recursive(arr, mid + 1, high, target); // search right half
    } else {
        return binary_search_recursive(arr, low, mid - 1, target); // search left half
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int result = binary_search_recursive(arr, 0, size - 1, target);
    if (result != -1) {
        printf("Found value %d at index %d\n", target, result);
    } else {
        printf("Value %d not found in array\n", target);
    }
    return 0;
}

if (low > high) {

base case: stop if search range is invalid (value not found)

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

calculate middle index to split search range

if (arr[mid] == target) {

check if middle element is the target value

return binary_search_recursive(arr, mid + 1, high, target);

search right half if target is greater than middle

return binary_search_recursive(arr, low, mid - 1, target);

search left half if target is less than middle

Output

Found value 9 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 dividing the search space repeatedly

Edge Cases

Empty array

Function returns -1 immediately as low > high

DSA C

if (low > high) {

Target not in array

Recursive calls narrow range until low > high, then return -1

DSA C

if (low > high) {

Single element array with target present

Check middle once and return index if matches

DSA C

if (arr[mid] == target) {

When to Use This Pattern

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

Common Mistakes

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

Mistake: Not updating low or high correctly in recursive calls
Fix: Set low to mid + 1 when searching right half, high to mid - 1 when searching left half

Mistake: Missing base case causing infinite recursion
Fix: Add base case: if low > high, return -1

Summary

It finds a target value in a sorted array by repeatedly dividing the search range in half using recursion.

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

The key insight is to compare the middle element and decide which half to search next, reducing the problem size quickly.

Practice

1. What is the main idea behind the binary search recursive approach when searching for an element in a sorted array?

easy

A. Check every element one by one from start to end

B. Divide the array into halves and search recursively in the half where the element can be

C. Sort the array first and then search linearly

D. Use a queue to store elements and search iteratively

Solution

1. Step 1: Understand binary search principle

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

2. Step 2: Apply recursion in binary search

   The recursive approach calls the same function on the half where the target element might be, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the half where the element can be -> Option B

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
• Not using recursion to reduce search space
• Searching unsorted arrays with binary search

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

easy

A. if (low == high) return -1;

B. if (low < high) return -1;

C. if (low > high) return -1;

D. if (low >= high) return -1;

Solution

1. Step 1: Understand base case in recursion

   The base case stops recursion when the search space is invalid, meaning low index is greater than high index.

2. Step 2: Identify correct condition

   When low > high, it means the element is not found, so return -1 to indicate failure.

3. Final Answer:

   if (low > high) return -1; -> Option C

4. Quick Check:

   Base case = low > high [OK]

Hint: Base case ends when low index passes high index [OK]

Common Mistakes:

• Using low == high as base case incorrectly
• Returning wrong value in base case
• Not handling base case leading to infinite recursion

3. What will be the output of the following C code snippet using recursive binary search?

int binarySearch(int arr[], int low, int high, int x) {
  if (low > high) return -1;
  int mid = low + (high - low) / 2;
  if (arr[mid] == x) return mid;
  else if (arr[mid] > x) return binarySearch(arr, low, mid - 1, x);
  else return binarySearch(arr, mid + 1, high, x);
}

int main() {
  int arr[] = {2, 4, 6, 8, 10};
  int n = 5;
  int result = binarySearch(arr, 0, n - 1, 6);
  printf("%d", result);
  return 0;
}

medium

A. 2

B. 1

C. -1

D. 3

Solution

1. Step 1: Trace the recursive calls

   Initial call: low=0, high=4, mid=2, arr[2]=6 equals target 6, so return 2 immediately.

2. Step 2: Understand output

   The function returns index 2 where element 6 is found, so printf prints 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Element 6 found at index 2 [OK]

Hint: Check mid index and compare to target first [OK]

Common Mistakes:

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

4. Identify the error in the following recursive binary search function and select the fix:

int binarySearch(int arr[], int low, int high, int x) {
  if (low >= high) return -1;
  int mid = (low + high) / 2;
  if (arr[mid] == x) return mid;
  else if (arr[mid] > x) return binarySearch(arr, low, mid - 1, x);
  else return binarySearch(arr, mid + 1, high, x);
}

medium

A. Return mid + 1 instead of mid when found

B. Change mid calculation to mid = low - (high - low) / 2;

C. Remove else if condition and use only if

D. Change base case to if (low > high) return -1;

Solution

1. Step 1: Analyze base case condition

   The base case uses if (low >= high) which incorrectly stops search when low equals high, missing the last element.

2. Step 2: Correct base case

   It should be if (low > high) to allow checking when low equals high, ensuring all elements are searched.

3. Final Answer:

   Change base case to if (low > high) return -1; -> Option D

4. Quick Check:

   Base case must allow low == high [OK]

Hint: Base case must be low > high, not low >= high [OK]

Common Mistakes:

• Stopping recursion too early
• Incorrect mid calculation causing infinite recursion
• Returning wrong index on match

5. Given a sorted array arr = {1, 3, 5, 7, 9, 11, 13}, you want to find the index of element 8 using recursive binary search. What will be the sequence of mid indices checked before concluding the element is not found?

hard

A. [3, 5, 4]

B. [3, 1, 0]

C. [3, 1, 2]

D. [3, 4, 5]

Solution

1. Step 1: Calculate first mid index

   Initial low=0, high=6, mid = (0+6)/2 = 3, arr[3]=7 less than 8, search right half next.

2. Step 2: Calculate second mid index

   New low=4, high=6, mid = (4+6)/2 = 5, arr[5]=11 greater than 8, search left half next.

3. Step 3: Calculate third mid index

   New low=4, high=4, mid = (4+4)/2 = 4, arr[4]=9 greater than 8, search left half next low=4, high=3 ends recursion.

4. Final Answer:

   [3, 5, 4] -> Option A

5. Quick Check:

   Mid indices checked = 3, 5, 4 [OK]

Hint: Track low, high, mid updates carefully each recursion [OK]

Common Mistakes:

• Not updating low and high correctly
• Miscomputing mid index
• Stopping search too early