Why Binary Search as Divide and Conquer in DSA Python?

The Big Idea

What if you could find anything in a huge list in just a few steps?

The Scenario

Imagine you have a huge phone book and you want to find one person's number. You start at the first page and look at every name one by one until you find the right one.

The Problem

This way is very slow and tiring because you might have to check many pages before finding the name. It wastes time and effort, especially if the book is very big.

The Solution

Binary Search splits the phone book in half each time you look. You check the middle page, decide which half the name is in, and then only search that half. This way, you quickly zoom in on the right page without checking every name.

Before vs After

✗ Before

def find_name(names, target):
    for name in names:
        if name == target:
            return True
    return False

✓ After

def binary_search(names, target):
    left, right = 0, len(names) - 1
    while left <= right:
        mid = (left + right) // 2
        if names[mid] == target:
            return True
        elif names[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

What It Enables

It lets you find items in sorted lists very fast, even if the list is huge.

Real Life Example

When you search for a word in a dictionary app, it uses binary search to quickly find the word instead of reading every word.

Key Takeaways

Manual search checks items one by one and is slow.

Binary Search cuts the search area in half each step.

This makes searching much faster for sorted data.

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