Binary Search as Divide and Conquer in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index in binary search.

DSA Python

mid = (low + [1]) // 2

Drag options to blanks, or click blank then click option'

Alow

Bhigh

Cmid

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using low twice instead of high.

Using mid variable before assignment.

The middle index is found by adding low and high, then dividing by 2.

2fill in blank

medium

Complete the code to check if the middle element is the target.

DSA Python

if arr[mid] [1] target:

Drag options to blanks, or click blank then click option'

A==

B<

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < or > instead of ==.

Using != which checks for inequality.

We check if the middle element equals the target to find it.

3fill in blank

hard

Fix the error in updating the low index when target is greater than middle element.

DSA Python

if arr[mid] < target:
    low = [1]

Drag options to blanks, or click blank then click option'

Amid

Bhigh

Cmid + 1

Dlow + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting low to mid causes infinite loop.

Using low + 1 ignores mid position.

When target is greater, we move low to mid + 1 to search the right half.

4fill in blank

hard

Fill both blanks to update high index when target is less than middle element.

DSA Python

if arr[mid] > target:
    high = [1] - [2]

Drag options to blanks, or click blank then click option'

Amid

B1

Clow

Dmid + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using mid + 1 increases high incorrectly.

Using low instead of mid.

We set high to mid - 1 to search the left half excluding mid.

5fill in blank

hard

Fill all three blanks to complete the binary search function.

DSA Python

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

Drag options to blanks, or click blank then click option'

Ahigh

Bmid

C1

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Returning low or high instead of mid.

Using 0 instead of 1 when updating low.

The function finds the middle index, returns mid if found, and moves low or high accordingly.

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