Binary Search Recursive Approach in DSA Python

Mental Model

Binary search splits a sorted list in half to find a target quickly by checking the middle element and searching only the half that could contain the target.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is in the first or second half, and repeating this until you find it.

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

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: Calculate mid index between low=0 and high=6, mid=3; compare array[mid]=7 with target=9

[1, 3, 5, 7, 9, 11, 13]
 low=0 ↑ mid=3 [7] ↑ high=6 ↑

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

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

[1, 3, 5, 7, 9, 11, 13]
 low=4 ↑ mid=? high=6 ↑

Why: Target must be in right half because 9 is greater than 7

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

[1, 3, 5, 7, 9, 11, 13]
 low=4 ↑ mid=5 [11] ↑ high=6 ↑

Why: Check middle of new subarray to narrow search

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

[1, 3, 5, 7, 9, 11, 13]
 low=4 ↑ mid=? high=4 ↑

Why: Target must be in left half because 9 is less than 11

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

[1, 3, 5, 7, 9, 11, 13]
 low=4 ↑ mid=4 [9] ↑ high=4 ↑

Why: Found the target at mid index

Result:

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

Annotated Code

DSA Python

from typing import List

def binary_search_recursive(arr: List[int], target: int, low: int, high: int) -> int:
    if low > high:
        return -1  # target not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid  # target found
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)  # search right half
    else:
        return binary_search_recursive(arr, target, low, mid - 1)  # search left half

# Driver code
array = [1, 3, 5, 7, 9, 11, 13]
target = 9
result = binary_search_recursive(array, target, 0, len(array) - 1)
if result != -1:
    print(f"Target {target} found at index {result}")
else:
    print(f"Target {target} not found in array")

if low > high:

check if search range is invalid, meaning target not found

mid = (low + high) // 2

calculate middle index of current search range

if arr[mid] == target:

check if middle element is the target

elif arr[mid] < target:

if middle element less than target, search right half

else:

if middle element greater than target, search left half

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 recursion call stack depth proportional to log n

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by cutting search space in half each step

Edge Cases

empty array

returns -1 immediately because low > high

DSA Python

if low > high:

target not in array

search narrows until low > high, then returns -1

DSA Python

if low > high:

single element array with target present

checks single element and returns index if match

DSA Python

if arr[mid] == target:

When to Use This Pattern

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

Common Mistakes

Mistake: Not updating low or high correctly in recursive calls causing infinite recursion
Fix: Ensure low is set to mid + 1 when searching right half and high is set to mid - 1 when searching left half

Summary

Binary search recursively finds a target in a sorted array by checking the middle and searching half the array each time.

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

The key insight is cutting the search space in half each step by comparing the middle element to the target.

Practice

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

easy

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

B. Sort the list first and then search linearly

C. Divide the list into halves and search recursively in the half where the target may exist

D. Use a queue to store elements and search iteratively

Solution

1. Step 1: Understand binary search logic

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

2. Step 2: Recognize recursive approach

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

3. Final Answer:

   Divide the list into halves and search recursively in the half where the target may exist -> Option C

4. Quick Check:

   Binary search = divide and conquer [OK]

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

Common Mistakes:

• Searching all elements linearly instead of dividing
• Not reducing the search space correctly
• Confusing iterative with recursive approach

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

easy

A. if low > high: return -1

B. if low == high: return mid

C. if mid == target: return low

D. if high < low: return mid

Solution

1. Step 1: Identify base case condition

   The base case occurs when the search space is empty, meaning low index is greater than high index.

2. Step 2: Confirm correct return value

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

3. Final Answer:

   if low > high: return -1 -> Option A

4. Quick Check:

   Empty search space means return -1 [OK]

Hint: Base case: low index passes high index means not found [OK]

Common Mistakes:

• Returning mid when low == high without checking target
• Using wrong comparison operators in base case
• Returning wrong index or value in base case

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

def binary_search(arr, low, high, target):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, low, mid - 1, target)
    else:
        return binary_search(arr, mid + 1, high, target)

arr = [2, 4, 6, 8, 10]
print(binary_search(arr, 0, len(arr) - 1, 6))

medium

A. 1

B. 2

C. -1

D. 3

Solution

1. Step 1: Trace initial call

   Call binary_search(arr, 0, 4, 6). mid = (0+4)//2 = 2. arr[2] = 6 matches target 6.

2. Step 2: Return mid index

   Since arr[mid] == target, function returns 2 immediately.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Target 6 found at index 2 [OK]

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

Common Mistakes:

• Calculating mid incorrectly
• Returning wrong index
• Confusing target value with index

4. Find the error in the following recursive binary search code:

def binary_search(arr, low, high, target):
    if low >= high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, low, mid - 1, target)
    else:
        return binary_search(arr, mid + 1, high, target)

medium

A. Recursive calls should swap low and high parameters

B. Mid calculation should be 'mid = (low + high + 1) // 2'

C. Return value should be 'None' instead of '-1'

D. Base case condition should be 'if low > high' instead of 'if low >= high'

Solution

1. Step 1: Analyze base case condition

   The base case incorrectly uses 'if low >= high', which misses the case when low == high and target is at that index.

2. Step 2: Correct base case to 'if low > high'

   Changing to 'if low > high' allows checking the last element when low == high before returning -1.

3. Final Answer:

   Base case condition should be 'if low > high' instead of 'if low >= high' -> Option D

4. Quick Check:

   Base case must allow checking last element [OK]

Hint: Base case: low > high means search ended [OK]

Common Mistakes:

• Using >= instead of > in base case
• Incorrect mid calculation
• Returning wrong value on failure

5. Given a sorted list arr = [1, 3, 5, 7, 9, 11, 13], write a recursive binary search function to find the index of the target 10. What will be the final output?

hard

A. -1

B. 4

C. 5

D. 6

Solution

1. Step 1: Trace recursive calls for target 10

   Initial call: low=0, high=6, mid=3, arr[3]=7 < 10, search right half (4 to 6). Next mid=5, arr[5]=11 > 10, search left half (4 to 4). Next mid=4, arr[4]=9 < 10, search right half (5 to 4). Now low=5 > high=4, base case reached.

2. Step 2: Return -1 as target not found

   Since low > high, function returns -1 indicating target 10 is not in the list.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   Target 10 not in list returns -1 [OK]

Hint: If target not found, recursive calls end with -1 [OK]

Common Mistakes:

• Assuming closest smaller element index is returned
• Not handling base case properly
• Confusing index with value