Binary Search Iterative Approach in DSA Python

Mental Model

Binary search finds a number by repeatedly cutting the search area in half until the number is found or no area remains.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is before or after that page, and repeating this until you find the word.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0   1   2   3   4    5    6
Pointers:  low ↑                 mid ↑                 high ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], target: 7

Goal: Find the index of 7 in the array using iterative binary search

Step 1: Set low to 0 and high to 6 (start and end of array)

low=0, high=6

Why: We start searching the whole array

Step 2: Calculate mid = (0 + 6) // 2 = 3, check array[mid] = 7

mid=3, array[mid]=7

Why: Mid divides the array to check the middle element

Step 3: array[mid] equals target 7, return index 3

Found target at index 3

Why: We found the target, so we stop searching

Result:

Index 3 where value 7 is found

Annotated Code

DSA Python

class BinarySearch:
    def __init__(self, arr):
        self.arr = arr

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

# Driver code
array = [1, 3, 5, 7, 9, 11, 13]
target = 7
bs = BinarySearch(array)
result = bs.search(target)
if result != -1:
    print(f"Index {result} where value {target} is found")
else:
    print("Target not found")

while low <= high:

keep searching while the search area is valid

mid = (low + high) // 2

find middle index to check

if self.arr[mid] == target:

check if middle element is the target

elif self.arr[mid] < target:

if middle element less than target, move low up

else:

if middle element greater than target, move high down

Output

Index 3 where value 7 is found

Complexity Analysis

Time: O(log n) because each step halves the search space

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 arrays by reducing steps exponentially

Edge Cases

empty array

returns -1 immediately since low > high

DSA Python

while low <= high:

target not in array

search narrows until low > high and returns -1

DSA Python

return -1

target is first element

found quickly when mid points to first index

DSA Python

if self.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 cuts the search space in half each step.

Common Mistakes

Mistake: Using mid = (low + high) without integer division causing float index
Fix: Use integer division // to get a valid index

Mistake: Not updating low or high correctly causing infinite loop
Fix: Update low to mid + 1 or high to mid - 1 depending on comparison

Summary

Finds the position of a target value in a sorted array by repeatedly dividing the search range.

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

The key is to cut the search space in half each time by comparing the middle element.

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