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.