Binary Search Iterative Approach in DSA Python - Execution Trace

Concept Flow - Binary Search Iterative Approach

Start with sorted array and target

↓

Set low = 0, high = len-1

↓

While low <= high

↓

Calculate mid = (low + high)//2

↓

Compare array[mid

↓

Return mid

↓

Repeat loop

↓

If not found, return -1

Start with low and high pointers on the sorted array ends, repeatedly check middle element, adjust pointers based on comparison until target is found or pointers cross.

Execution Sample

DSA Python

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

This code searches for target in a sorted array using an iterative binary search, returning the index or -1 if not found.

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Pointer Changes	Visual State
1	Initialize low and high	0	6	-	-	-	low=0, high=6	[2, 4, 6, 8, 10, 12, 14]
2	Calculate mid	0	6	3	8	8 == 10? No	None	[2, 4, 6, 8, 10, 12, 14]
3	Compare arr[mid] < target	0	6	3	8	8 < 10? Yes	low = mid + 1 = 4	[2, 4, 6, 8, 10, 12, 14]
4	Calculate mid	4	6	5	12	12 == 10? No	None	[2, 4, 6, 8, 10, 12, 14]
5	Compare arr[mid] > target	4	6	5	12	12 > 10? Yes	high = mid - 1 = 4	[2, 4, 6, 8, 10, 12, 14]
6	Calculate mid	4	4	4	10	10 == 10? Yes	Return mid = 4	[2, 4, 6, 8, 10, 12, 14]

💡 Target found at index 4, loop ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
low	0	0	4	4	4	4	4
high	6	6	6	6	4	4	4
mid	-	3	3	5	5	4	4
arr[mid]	-	8	8	12	12	10	10

Key Moments - 3 Insights

Why do we update 'low' to mid + 1 when arr[mid] < target?

Because arr[mid] is less than target, the target must be in the right half, so we move 'low' just after 'mid' to exclude mid and left side. See execution_table row 3.

Why does the loop stop when low > high?

When low passes high, it means the search space is empty and target is not found. The loop condition low <= high ensures we only search valid ranges. This is shown by the loop condition in concept_flow.

Why do we calculate mid as (low + high) // 2 each time?

Because mid is the middle index between low and high, dividing the search space in half each iteration. This is shown in execution_table steps 2, 4, and 6.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of 'low' after the pointer change?

A 0

B 3

C 4

D 6

💡 Hint

Check the 'Pointer Changes' column in execution_table row 3.

At which step does the condition low <= high become false, ending the loop?

A Step 6

B After Step 6

C Step 5

D After Step 5

💡 Hint

The loop ends after finding the target at Step 6, so condition fails after Step 6.

If the target was 13 instead of 10, what would happen to 'high' at Step 5?

A high would be set to 5

B high would remain 6

C high would be set to 4

D high would be set to 3

💡 Hint

Look at how 'high' changes when arr[mid] > target in execution_table row 5.

Concept Snapshot

Binary Search Iterative Approach:
- Works on sorted arrays
- Use two pointers: low and high
- Calculate mid = (low + high)//2
- Compare arr[mid] with target
- If equal, return mid
- If arr[mid] < target, move low to mid+1
- Else, move high to mid-1
- Repeat until low > high
- Return -1 if not found

Full Transcript

Binary Search Iterative Approach starts with a sorted array and two pointers, low and high, at the ends. It calculates the middle index mid and compares the middle element with the target. If they match, it returns the index. If the middle element is less than the target, it moves the low pointer just after mid to search the right half. If greater, it moves the high pointer just before mid to search the left half. This repeats until low passes high, meaning the target is not found. The execution table shows each step with pointer values and comparisons. Key moments clarify why pointers move and when the loop ends. The visual quiz tests understanding of pointer updates and loop termination. This approach efficiently finds elements in sorted arrays by halving the search space each iteration.

Practice

1. What is the main purpose of the mid variable in the iterative binary search algorithm?

easy

A. To store the target value we are searching for

B. To keep track of the number of iterations

C. To find the middle index of the current search range

D. To hold the entire list being searched

Solution

1. Step 1: Understand the role of mid in binary search

   The mid variable calculates the middle index between the current low and high indices to split the search range.

2. Step 2: Explain why mid is important

   By checking the element at mid, the algorithm decides whether to search the left or right half next.

3. Final Answer:

   To find the middle index of the current search range -> Option C

4. Quick Check:

   mid = middle index [OK]

Hint: Remember binary search splits list by middle index [OK]

Common Mistakes:

• Confusing mid with the target value
• Using mid as a counter instead of index
• Not updating mid inside the loop

2. Which of the following is the correct way to calculate the middle index mid in an iterative binary search in Python?

easy

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

B. mid = low - high // 2

C. mid = low + high

D. mid = (low + high) / 2

Solution

1. Step 1: Identify correct integer division in Python

   In Python, // performs integer division, which is needed for an index.

2. Step 2: Explain why / is incorrect

   / returns a float, which cannot be used as a list index.

3. Final Answer:

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

4. Quick Check:

   Use integer division for index [OK]

Hint: Use // for integer division in Python [OK]

Common Mistakes:

• Using / which returns float
• Adding low and high without division
• Incorrect operator precedence without parentheses

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

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. 1

B. 3

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.

2. Step 2: Return the index where target is found

   Since arr[mid] == target, function returns 2 immediately.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Index of 6 in array is 2 [OK]

Hint: Check mid index value first to find target fast [OK]

Common Mistakes:

• Confusing index with value
• Returning value instead of index
• Off-by-one errors in mid calculation

4. Identify the error in the following iterative binary search code:

def binary_search(arr, target):
    low = 0
    high = 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. high should be initialized as len(arr) - 1

B. low should start from 1 instead of 0

C. mid calculation should use float division

D. The loop condition should be while low < high

Solution

1. Step 1: Check initialization of high

   High is set to len(arr), which is out of valid index range (0 to len(arr)-1).

2. Step 2: Explain correct initialization

   High should be len(arr) - 1 to avoid index out of range errors when accessing arr[mid].

3. Final Answer:

   high should be initialized as len(arr) - 1 -> Option A

4. Quick Check:

   High = len(arr) - 1 for valid index [OK]

Hint: Array indices go from 0 to length-1 [OK]

Common Mistakes:

• Setting high to len(arr) causes index error
• Changing low start incorrectly
• Using float division for mid

5. Given a sorted list arr = [1, 3, 5, 7, 9, 11, 13], how many iterations will the iterative binary search take to find the target 7?

medium

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace iterations to find 7

   Iteration 1: low=0, high=6, mid=3, arr[3]=7 matches target.

2. Step 2: Count iterations

   Since target found at first mid check, total iterations = 1.

3. Step 3: Reconsider counting loop passes

   Loop runs once, but mid calculation and comparison count as one iteration.

4. Final Answer:

   1 -> Option B

5. Quick Check:

   Target found at first mid check [OK]

Hint: Count each mid calculation as one iteration [OK]

Common Mistakes:

• Counting iterations incorrectly
• Assuming always 3 iterations for 7 elements
• Confusing iterations with index value