Binary Search Iterative Approach in DSA Python - Build from Scratch

Binary Search Iterative Approach

📖 Scenario: You have a sorted list of book page numbers. You want to find if a certain page number exists in the book quickly.

🎯 Goal: Build a program that uses the binary search iterative method to find a page number in a sorted list.

📋 What You'll Learn

Create a sorted list of page numbers

Set the target page number to search for

Implement the binary search using a while loop

Print the index of the target page if found, or -1 if not found

💡 Why This Matters

🌍 Real World

Binary search is used in many applications like searching in phone books, dictionaries, or any sorted data quickly.

💼 Career

Understanding binary search helps in software development roles where efficient searching algorithms improve performance.

1

Create the sorted list of page numbers

Create a list called pages with these exact values: [3, 8, 15, 23, 42, 56, 78, 91]

DSA Python

# Create the list called pages with the given values
# Your code here

Hint

Use square brackets and commas to create the list exactly as shown.

2

Set the target page number to search

Create a variable called target and set it to 42

DSA Python

pages = [3, 8, 15, 23, 42, 56, 78, 91]
# Create the variable target and set it to 42
# Your code here

Hint

Just assign the number 42 to the variable named target.

3

Implement the binary search iterative logic

Write code to perform binary search iteratively using variables left, right, and mid. Use a while loop that runs while left <= right. Inside the loop, calculate mid as the middle index, compare pages[mid] with target, and adjust left or right accordingly. Create a variable result that stores the index if found, or -1 if not found.

DSA Python

pages = [3, 8, 15, 23, 42, 56, 78, 91]
target = 42
# Implement the binary search iterative logic below
# Your code here

Hint

Use a while loop and update left and right pointers based on comparison with target.

4

Print the search result

Print the value of the variable result to show the index of the target page or -1 if not found.

DSA Python

pages = [3, 8, 15, 23, 42, 56, 78, 91]
target = 42
left = 0
right = len(pages) - 1
result = -1
while left <= right:
    mid = (left + right) // 2
    if pages[mid] == target:
        result = mid
        break
    elif pages[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
# Print the result variable
# Your code here

Hint

Use print(result) to show the index.

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