Binary Search Recursive Approach in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search on Sorted List

What is the output of this code when searching for the value 7 in the list?

DSA Python

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

arr = [1, 3, 5, 7, 9, 11]
result = binary_search(arr, 0, len(arr) - 1, 7)
print(result)

A 4

B 2

C -1

D 3

💡 Hint

Remember that list indices start at 0 and binary search returns the index of the found element.

The value 7 is at index 3 in the list. The recursive binary search finds it and returns 3.

❓ Predict Output

intermediate

Result of Searching Missing Element

What will be printed when searching for 8 in the list using the recursive binary search?

DSA Python

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

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

A -1

B 2

C 3

D 0

💡 Hint

If the element is not found, the function returns -1.

The value 8 is not in the list, so the function returns -1 indicating not found.

🔧 Debug

advanced

Identify the Error in Recursive Binary Search

What error will this code produce when run?

DSA Python

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

arr = [1, 2, 3, 4, 5]
print(binary_search(arr, 0, len(arr) - 1, 5))

A IndexError

B Returns -1 even if element is present

C SyntaxError

D Returns correct index 2

💡 Hint

Check the base condition for recursion termination carefully.

The base condition uses 'high > low' instead of 'high >= low', so when low equals high, the function does not check that element and returns -1 incorrectly.

🧠 Conceptual

advanced

Number of Recursive Calls in Binary Search

If you perform a recursive binary search on a sorted list of 64 elements, what is the maximum number of recursive calls made before the search ends?

A 8

B 9

C 7

D 6

💡 Hint

Binary search halves the search space each call. Think about powers of 2.

Binary search divides the search space by 2 in each recursive call. For a list of 64 elements (2^6), the worst-case number of recursive calls is log₂(64) + 1 = 7.

❓ Predict Output

expert

Output of Recursive Binary Search with Duplicate Elements

What index will the recursive binary search return when searching for 5 in this list?

DSA Python

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

arr = [1, 3, 5, 5, 5, 7, 9]
print(binary_search(arr, 0, len(arr) - 1, 5))

A 3

B 2

C 4

D -1

💡 Hint

Binary search may return any index of the target if duplicates exist.

The middle index is calculated as (0+6)//2=3. The element at index 3 is 5, so the function returns 3 immediately.

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