Binary Search as Divide and Conquer in DSA Python - Execution Trace

Concept Flow - Binary Search as Divide and Conquer

Start with sorted array and target

↓

Find middle element index

↓

Compare middle element with target

↓

Return index

↓

Search left half

↓

Repeat steps

Binary search splits the sorted array into halves, compares the middle element with the target, and recursively searches the half where the target can be.

Execution Sample

DSA Python

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

This code searches for a target value in a sorted array by repeatedly dividing the search interval in half.

Execution Table

Step	Operation	Left Index	Right Index	Mid Index	Mid Value	Comparison	Action	Array State
1	Initialize	0	6	-	-	-	Start search	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 == 9?	No, 9 > 7	[1, 3, 5, 7, 9, 11, 13]
3	Update left	4	6	-	-	-	Search right half	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	6	5	11	11 == 9?	No, 9 < 11	[1, 3, 5, 7, 9, 11, 13]
5	Update right	4	4	-	-	-	Search left half	[1, 3, 5, 7, 9, 11, 13]
6	Calculate mid	4	4	4	9	9 == 9?	Yes, found target	[1, 3, 5, 7, 9, 11, 13]
7	Return	-	-	-	-	-	Return index 4	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	4	4	4	4	4
right	6	6	6	6	4	4	4
mid	-	3	-	5	-	4	4
mid_value	-	7	-	11	-	9	9

Key Moments - 3 Insights

Why do we update 'left' to mid + 1 when target is greater than mid value?

Because the target cannot be at mid or any index less than mid, so we move 'left' to mid + 1 to search only the right half, as shown in step 3 of the execution_table.

Why do we stop the search when left > right?

When 'left' becomes greater than 'right', it means the search space is empty and the target is not found. This condition ends the loop, as implied after step 7.

Why do we calculate mid as (left + right) // 2?

Calculating mid this way finds the middle index between left and right, dividing the array into two halves for the next search step, as seen in steps 2, 4, and 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 4?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'Mid Index' column in row for step 4 in execution_table.

At which step does the 'right' pointer get updated to 4?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Right Index' column changes in execution_table rows.

If the target was 12 instead of 9, what would happen at step 5?

A Right pointer would update to 4

B Left pointer would update to 6

C Search would end with target found

D Mid index would be recalculated as 5

💡 Hint

Think about how the pointers move when target is greater than mid value, referencing steps 2 and 3.

Concept Snapshot

Binary Search divides a sorted array by checking the middle element.
If middle equals target, return index.
If target is less, search left half.
If target is more, search right half.
Repeat until found or search space is empty.
Efficient with O(log n) time complexity.

Full Transcript

Binary Search works on a sorted array by repeatedly dividing the search range in half. We start with left and right pointers at the ends of the array. We find the middle index and compare its value to the target. If equal, we return the index. If the target is smaller, we move the right pointer to mid - 1 to search the left half. If larger, we move the left pointer to mid + 1 to search the right half. This repeats until the target is found or the pointers cross, meaning the target is not in the array.

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