Binary Search Iterative Approach in DSA C++

Mental Model

Binary search repeatedly cuts the list in half to find a target value quickly.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if you should look in the first or second half, 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 ↑                 high ↑
Middle:          mid ↑

Dry Run Walkthrough

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

Goal: Find the index of the target value 7 using iterative binary search

Step 1: Calculate mid index between low=0 and high=6

low=0, mid=3, high=6, array[mid]=7

Why: We check the middle element to decide which half to search next

Step 2: Compare array[mid] with target; they are equal

Found target at index 3

Why: If middle element equals target, search ends successfully

Result:

Index 3 is the position of target 7 in the array

Annotated Code

DSA C++

#include <iostream>
#include <vector>

int binarySearchIterative(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = static_cast<int>(arr.size()) - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // avoid overflow
        if (arr[mid] == target) {
            return mid;  // target found
        } else if (arr[mid] < target) {
            low = mid + 1;  // search right half
        } else {
            high = mid - 1;  // search left half
        }
    }
    return -1;  // target not found
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;
    int index = binarySearchIterative(arr, target);
    if (index != -1) {
        std::cout << "Target found at index: " << index << std::endl;
    } else {
        std::cout << "Target not found" << std::endl;
    }
    return 0;
}

int mid = low + (high - low) / 2; // avoid overflow

Calculate middle index between low and high

if (arr[mid] == target) {

Check if middle element is the target

return mid; // target found

Return index if target found

else if (arr[mid] < target) {

If middle element less than target, search right half

low = mid + 1; // search right half

Move low pointer to mid+1 to narrow search

else {

If middle element greater than target, search left half

high = mid - 1; // search left half

Move high pointer to mid-1 to narrow search

Output

Target found at index: 3

Complexity Analysis

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

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

Edge Cases

Empty array

Returns -1 immediately since low > high

DSA C++

while (low <= high) {

Target not in array

Search narrows until low > high, then returns -1

DSA C++

return -1;  // target not found

Single element array with target

Returns index 0 immediately if element matches target

DSA C++

if (arr[mid] == target) {

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search iterative approach because it efficiently halves the search space each step.

Common Mistakes

Mistake: Calculating mid as (low + high) / 2 can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly causing infinite loop
Fix: Ensure low = mid + 1 or high = mid - 1 to shrink search space

Mistake: Using while (low < high) instead of while (low <= high) misses last element
Fix: Use while (low <= high) to include all elements

Summary

Binary search finds a target in a sorted array by repeatedly dividing the search range in half.

Use it when you have a sorted list and want fast search performance.

The key insight is to compare the middle element and discard half the search space each time.

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