Why Binary Search and What Sorted Order Gives You in DSA C++ - Why This Pattern

Mental Model

Binary search quickly finds a value by repeatedly cutting the search area in half, but it only works if the list is sorted.

Analogy: Imagine looking for a word in a dictionary: you open it in the middle, decide if your word is before or after, then open the right half again and again until you find it.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15]
Indices:      0      1      2      3      4       5       6       7

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13, 15], search for value 9

Goal: Find the position of value 9 quickly using binary search

Step 1: Check middle element at index 3 (value 7)

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> [15]

Why: We start by looking at the middle to decide which half to search next

Step 2: Since 9 > 7, search right half from index 4 to 7

[9] -> [11] -> [13] -> [15]

Why: Because 9 is bigger than 7, it must be in the right half

Step 3: Check middle element at index 5 (value 11)

[9] -> [11↑] -> [13] -> [15]

Why: Look at the middle of the new search area to narrow down further

Step 4: Since 9 < 11, search left half from index 4 to 4

[9]

Why: Because 9 is smaller than 11, it must be in the left half

Step 5: Check element at index 4 (value 9), found target

[9↑]

Why: We found the value we were searching for

Result:

[9↑] at index 4

Annotated Code

DSA C++

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // find middle index
        if (arr[mid] == target) {
            return mid; // found target
        } else if (arr[mid] < target) {
            left = mid + 1; // search right half
        } else {
            right = mid - 1; // search left half
        }
    }
    return -1; // target not found
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 9;
    int index = binarySearch(arr, target);
    if (index != -1) {
        std::cout << "Found " << target << " at index " << index << "\n";
    } else {
        std::cout << target << " not found in array\n";
    }
    return 0;
}

int mid = left + (right - left) / 2; // find middle index

Calculate middle index to split search area

if (arr[mid] == target) { return mid; }

Check if middle element is the target

else if (arr[mid] < target) { left = mid + 1; }

If target is bigger, move left pointer to right half

else { right = mid - 1; }

If target is smaller, move right pointer to left half

Output

Found 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space, quickly narrowing down to the target

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search's O(n), binary search is much faster on sorted data by skipping half the elements each step

Edge Cases

empty array

returns -1 immediately because left > right

DSA C++

while (left <= right) {

target smaller than all elements

search narrows until left > right, returns -1

DSA C++

while (left <= right) {

target larger than all elements

search narrows until left > right, returns -1

DSA C++

while (left <= right) {

When to Use This Pattern

When you need to find an item quickly in a sorted list, reach for binary search because it cuts the search space in half each step.

Common Mistakes

Mistake: Not ensuring the list is sorted before binary search
Fix: Always sort the list first or confirm it is sorted before applying binary search

Mistake: Calculating middle index as (left + right) / 2 causing overflow
Fix: Use left + (right - left) / 2 to avoid integer overflow

Summary

Binary search finds a target value quickly by repeatedly dividing the search area in half.

Use binary search when you have a sorted list and want fast search times.

The key insight is that sorted order lets you skip half the elements each step, making search much faster.