Binary Search as Divide and Conquer in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search Call

What is the output of the following Python code that uses recursive binary search to find the index of the number 7 in the list?

DSA Python

def binary_search(arr, low, high, x):
    if low > high:
        return -1
    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)

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

A -1

B 2

C 4

D 3

💡 Hint

Think about the middle index and how the search narrows down.

The list is [1,3,5,7,9,11]. The middle index is 2 (value 5). Since 7 > 5, search right half. Next mid is 3 (value 7), found at index 3.

🧠 Conceptual

intermediate

Divide and Conquer in Binary Search

Which statement best describes how binary search uses the divide and conquer approach?

A It searches both halves of the list simultaneously to find the target faster.

B It divides the list into two halves and recursively searches only the half that may contain the target.

C It divides the list into multiple parts and searches all parts in parallel.

D It combines all elements into one and searches linearly.

💡 Hint

Think about how the search space reduces each step.

Binary search splits the list into two halves and only continues searching the half where the target could be, ignoring the other half.

❓ Predict Output

advanced

Output of Binary Search with Missing Element

What is the output of this code when searching for 8 in the sorted list?

DSA Python

def binary_search(arr, low, high, x):
    if low > high:
        return -1
    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)

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

A 3

B 2

C -1

D 0

💡 Hint

If the element is not found, what does the function return?

8 is not in the list. The function returns -1 when the search space is empty.

🔧 Debug

advanced

Identify the Error in Binary Search Implementation

What error will this binary search code produce when searching for 7 in the list?

DSA Python

def binary_search(arr, low, high, x):
    if low >= high:
        return -1
    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)

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

A Returns -1 even if element is present

B Correctly returns index 3

C Infinite recursion causing RecursionError

D IndexError due to invalid mid calculation

💡 Hint

Check the base case condition carefully.

The base case uses 'low >= high' which excludes the case when low == high, missing the last element check. So it returns -1 even if element is present.

🚀 Application

expert

Number of Recursive Calls in Binary Search

Given a sorted list of 64 elements, what is the maximum number of recursive calls binary search will make to find an element or conclude it is not present?

A 7

B 6

C 9

D 8

💡 Hint

Think about how many times you can divide 64 by 2 until you reach 1.

Binary search divides the search space in half each recursive call. For 64 elements (2^6), the worst case requires 7 recursive calls: log2(64) + 1 = 7.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It uses random guesses to find the target quickly.

B. It searches every element one by one until it finds the target.

C. It divides the search range in half each time to find the target efficiently.

D. It sorts the array before searching for the target.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the sorted list into two halves and decides which half to search next.

2. Step 2: How binary search reduces search space

   By halving the search range each time, it quickly narrows down where the target could be.

3. Final Answer:

   It divides the search range in half each time to find the target efficiently. -> Option C

4. Quick Check:

   Divide and conquer = halve search space [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Thinking binary search checks every element
• Assuming binary search works on unsorted lists
• Confusing binary search with linear search

2. Which of the following is the correct Python syntax to calculate the middle index in binary search for a list named arr with indices low and high?

easy

A. mid = (low + high) // 2

B. mid = (low + high) / 2

C. mid = low + high

D. mid = low - high // 2

Solution

1. Step 1: Understand integer division for index calculation

   We need an integer index, so floor division (//) is used to get the middle index.

2. Step 2: Check each option for correctness

   mid = (low + high) // 2 uses floor division correctly. mid = (low + high) / 2 uses float division, which is invalid for indexing. Options C and D do not calculate the middle index properly.

3. Final Answer:

   mid = (low + high) // 2 -> Option A

4. Quick Check:

   Use floor division for middle index [OK]

Hint: Use // for integer middle index in Python [OK]

Common Mistakes:

• Using / which gives float index
• Adding indices without dividing
• Incorrect operator precedence

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

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

arr = [2, 4, 6, 8, 10]
print(binary_search(arr, 6))

medium

A. 3

B. 1

C. -1

D. 2

Solution

1. Step 1: Trace the binary search for target 6

   Initial low=0, high=4, mid=2. arr[2]=6 matches target, so return 2.

2. Step 2: Confirm returned index

   The function returns index 2 where 6 is found.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check mid index value matches target first [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Returning -1 incorrectly

4. Identify the error in the following binary search code and choose the correct fix.

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

medium

A. Change 'high = len(arr)' to 'high = len(arr) - 1' to avoid index error.

B. Change 'low <= high' to 'low < high' to fix infinite loop.

C. Change 'mid = (low + high) // 2' to 'mid = (low + high + 1) // 2' for correct mid.

D. Remove 'return -1' to allow function to run longer.

Solution

1. Step 1: Check initialization of high index

   Using 'high = len(arr)' causes out-of-range error because last valid index is len(arr) - 1.

2. Step 2: Correct high initialization

   Set 'high = len(arr) - 1' to ensure mid index stays within valid range.

3. Final Answer:

   Change 'high = len(arr)' to 'high = len(arr) - 1' to avoid index error. -> Option A

4. Quick Check:

   High index must be last valid index [OK]

Hint: Set high to last index, not length [OK]

Common Mistakes:

• Setting high to length causes index error
• Changing loop condition incorrectly
• Miscalculating mid index

5. Given a sorted list arr = [1, 3, 5, 7, 9, 11, 13], you want to find the smallest index where the value is greater than or equal to 8 using binary search. Which modification to the standard binary search will achieve this?

hard

A. Use linear search instead because binary search can't find this.

B. Adjust binary search to move 'high' to mid - 1 when arr[mid] >= 8, else move 'low' to mid + 1.

C. Return mid immediately when arr[mid] > 8 without further checks.

D. Modify binary search to always move 'low' to mid + 1 regardless of comparison.

Solution

1. Step 1: Understand the problem - find smallest index with value >= 8

   This is a variant called lower bound search, requiring careful adjustment of pointers.

2. Step 2: Modify binary search to narrow down to smallest qualifying index

   When arr[mid] >= 8, move 'high' to mid - 1 to check if smaller index also qualifies; else move 'low' to mid + 1.

3. Final Answer:

   Adjust binary search to move 'high' to mid - 1 when arr[mid] >= 8, else move 'low' to mid + 1. -> Option B

4. Quick Check:

   Lower bound search moves high left on >= condition [OK]

Hint: Move high left when mid value meets condition [OK]

Common Mistakes:

• Returning immediately without checking smaller indices
• Using linear search unnecessarily
• Moving low pointer incorrectly