Binary Search Iterative Approach in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search finds an item in a sorted list by repeatedly dividing the search range in half until the item is found or the range is empty.

beginner

In the iterative binary search, what variables are used to keep track of the search range?

Two variables, usually called low and high, mark the start and end of the current search range in the list.

intermediate

Why do we calculate the middle index as mid = low + (high - low) // 2 instead of (low + high) // 2?

Calculating mid this way avoids potential overflow errors when low and high are very large numbers.

beginner

What condition ends the iterative binary search loop?

The loop ends when low becomes greater than high, meaning the search range is empty and the item is not found.

beginner

What is the time complexity of the binary search algorithm?

Binary search runs in O(log n) time, where n is the number of elements in the list.

What must be true about the list for binary search to work correctly?

A The list must contain only unique elements

B The list must be unsorted

C The list must be sorted

D The list must be empty

Binary search requires the list to be sorted to correctly divide and conquer the search space.

In iterative binary search, what happens if the target is less than the middle element?

A Search continues in the right half

B Search continues in the left half

C Search ends immediately

D The middle element is returned

If the target is less than the middle element, the search continues in the left half by updating the high index.

Which variable is updated when the target is greater than the middle element in iterative binary search?

A low

B high

C mid

D target

When the target is greater, the low index is updated to narrow the search to the right half.

What is the initial value of low in iterative binary search?

A 0

B Length of the list

C Middle index

D -1

low starts at 0, the first index of the list.

What does the iterative binary search return if the target is not found?

A Middle index

B 0

C Length of the list

D -1

Returning -1 is a common way to indicate the target is not found in the list.

Explain how the iterative binary search algorithm works step-by-step.

Think about how you cut the search space in half each time.

Describe why binary search is faster than linear search on sorted lists.

Consider how many elements you skip each step.

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