Binary Search as Divide and Conquer in DSA Python

Mental Model

Binary search splits a sorted list into halves to quickly find a target value by ignoring half the list each time.

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

Sorted list: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Indices:    0      1      2      3      4       5       6
Search range: ↑start                 ↑mid                 ↑end

Dry Run Walkthrough

Input: list: [1, 3, 5, 7, 9, 11, 13], search for 9

Goal: Find the index of value 9 in the sorted list using binary search

Step 1: Calculate mid index between start=0 and end=6; mid=3; check value at mid=7

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
start=0, mid=3 (value=7), end=6

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

Step 2: Since 9 > 7, move start to mid+1=4 to search right half

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
start=4, end=6

Why: Target is greater than mid value, so ignore left half

Step 3: Calculate mid index between start=4 and end=6; mid=5; check value at mid=11

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
start=4, mid=5 (value=11), end=6

Why: Check middle of new search range

Step 4: Since 9 < 11, move end to mid-1=4 to search left half

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
start=4, end=4

Why: Target is less than mid value, so ignore right half

Step 5: Calculate mid index between start=4 and end=4; mid=4; check value at mid=9

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
start=4, mid=4 (value=9), end=4

Why: Check the last remaining element

Step 6: Value at mid equals target 9; return index 4

[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13]
Found target at index 4

Why: Target found, stop searching

Result:

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

Annotated Code

DSA Python

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

# Driver code
arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
index = binary_search(arr, target)
if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found in the list")

mid = (start + end) // 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

start = mid + 1

Move start pointer to right half

else:

If middle element greater than target, search left half

end = mid - 1

Move end pointer to left half

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range, quickly narrowing down the target

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted lists by skipping half the elements each step

Edge Cases

Empty list

Returns -1 immediately as start > end

DSA Python

while start <= end:

Target not in list

Search narrows until start > end, then returns -1

DSA Python

return -1

Single element list where element is target

Returns index 0 immediately

DSA Python

if arr[mid] == target:

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it divides the problem in half each time, making search very fast.

Common Mistakes

Mistake: Calculating mid as (start + end) without integer division
Fix: Use integer division (start + end) // 2 to get a valid index

Mistake: Not updating start or end correctly causing infinite loop
Fix: Ensure start = mid + 1 or end = mid - 1 to shrink search range

Mistake: Using binary search on unsorted list
Fix: Sort the list first or use linear search instead

Summary

Binary search finds a target in a sorted list by repeatedly dividing the search range in half.

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

The key insight is that each comparison lets you ignore half the remaining elements.

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