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

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search repeatedly divides a sorted list in half to find a target value quickly by comparing the middle element and deciding which half to search next.

beginner

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

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

intermediate

Why is the middle index calculated as mid = low + (high - low) / 2 instead of (low + high) / 2?

Calculating mid as low + (high - low) / 2 prevents integer overflow when low and high are large numbers.

beginner

What condition ends the iterative binary search loop?

The loop ends when low becomes greater than high, meaning the target is not found in the list.

beginner

What is the time complexity of the binary search algorithm?

The time complexity is O(log n), meaning the search time grows logarithmically with the size of the list.

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

A The list must be sorted

B The list must be unsorted

C The list must contain only unique elements

D The list must be empty

Binary search requires the list to be sorted to correctly decide which half to search next.

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

A Search the left half

B Search the right half

C Return the middle index immediately

D Stop the search

If the middle element is less than the target, the search continues in the right half by moving the low pointer.

What does the variable high represent in binary search?

A The start index of the search range

B The middle index of the list

C The target value

D The end index of the search range

high marks the end index of the current search range.

What happens if the target value is not found in the list after the binary search completes?

A The function returns the last middle index

B The function throws an error

C The function returns -1 or a not found indicator

D The function returns 0

If the target is not found, the search ends and returns -1 or another indicator to show absence.

What is the advantage of using an iterative approach over a recursive approach in binary search?

A Iterative uses less memory by avoiding function call overhead

B Iterative is slower than recursive

C Iterative cannot handle large lists

D Iterative is harder to understand

Iterative binary search avoids the overhead of recursive calls, using less memory and often running faster.

Explain step-by-step how the iterative binary search algorithm finds a target in a sorted list.

Think about how the search range shrinks each step.

Describe why binary search is more efficient than linear search on large sorted lists.

Consider how many elements are checked in each method.

Practice

1. What is the main purpose of the binarySearchIterative function in the iterative binary search approach?

easy

A. To find the position of a target value in a sorted array

B. To sort an unsorted array

C. To reverse the elements of an array

D. To count the number of elements in an array

Solution

1. Step 1: Understand the function goal

   The binary search function is designed to locate a target value within a sorted array efficiently.

2. Step 2: Identify the operation performed

   It repeatedly divides the search interval in half to find the target's position or determine it is not present.

3. Final Answer:

   To find the position of a target value in a sorted array -> Option A

4. Quick Check:

   Binary search locates target index [OK]

Hint: Binary search finds target index in sorted array fast [OK]

Common Mistakes:

• Thinking binary search sorts the array
• Confusing binary search with linear search
• Assuming it works on unsorted arrays

2. Which of the following is the correct syntax to calculate the middle index in an iterative binary search to avoid overflow?

easy

A. int mid = (low - high) / 2;

B. int mid = (low + high) / 2;

C. int mid = low + (high - low) / 2;

D. int mid = (high - low) / 2 + high;

Solution

1. Step 1: Understand overflow risk in mid calculation

   Using (low + high) / 2 can overflow if low and high are large integers.

2. Step 2: Use safe formula to avoid overflow

   The formula low + (high - low) / 2 calculates mid without adding large numbers directly.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option C

4. Quick Check:

   Safe mid calculation avoids overflow [OK]

Hint: Use low + (high - low)/2 to prevent overflow [OK]

Common Mistakes:

• Using (low + high)/2 causing overflow
• Subtracting incorrectly in mid calculation
• Mixing up low and high in formula

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

int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int target = 6;
int result = binarySearchIterative(arr, n, target);
std::cout << result << std::endl;

// Assume binarySearchIterative is correctly implemented iterative binary search

medium

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Identify the target and array

   The array is {2, 4, 6, 8, 10} and the target is 6.

2. Step 2: Find the index of target using binary search

   6 is at index 2 (0-based indexing) in the array.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Remember array indexing starts at 0 [OK]

Common Mistakes:

• Confusing index with value
• Using 1-based indexing instead of 0-based
• Assuming target not found returns 0

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

int binarySearchIterative(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

medium

A. The mid calculation can cause integer overflow

B. The loop condition should be low < high

C. The return value should be 0 when not found

D. The array should be unsorted for binary search

Solution

1. Step 1: Review mid calculation

   Mid is calculated as (low + high) / 2 which can overflow if low and high are large.

2. Step 2: Suggest safer mid calculation

   Use low + (high - low) / 2 to avoid overflow in mid calculation.

3. Final Answer:

   The mid calculation can cause integer overflow -> Option A

4. Quick Check:

   Mid calculation overflow risk = true [OK]

Hint: Use safe mid formula to avoid overflow [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Returning 0 instead of -1 when not found
• Assuming binary search works on unsorted arrays

5. Given a sorted array arr = {1, 3, 5, 7, 9, 11, 13}, how many iterations will the iterative binary search take to find the target value 7?

hard

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Initialize low and high pointers

   low = 0, high = 6 (array length - 1)

2. Step 2: Trace each iteration to find 7

   Iteration 1: mid = 0 + (6-0)/2 = 3, arr[3] = 7 (target found at first check)

3. Step 3: Count iterations

   Only 1 iteration is needed because target is found immediately at mid index 3.

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Target found at first mid check [OK]

Hint: Count mid calculations until target found [OK]

Common Mistakes:

• Assuming always 3 iterations for any search
• Counting array length instead of iterations
• Forgetting zero-based indexing