Searching: Linear and Binary Search

The most common task: finding something

Searching is everywhere — find a user by ID, check if a value exists, look up a price. The simplest approach is linear search: start at the beginning and check each element until you find your target or run out.

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;          // found it — return the position
        }
    }
    return -1;                 // not found
}

int main() {
    int arr[] = {5, 2, 9, 1, 7};
    cout << linearSearch(arr, 5, 9);   // 2
    return 0;
}

Linear search is O(n) — in the worst case (target at the end or absent) you check every element. It always works, on any data, sorted or not. But for large datasets, "check everything" is too slow.

Binary search: the power of sorted data

If your data is sorted, you can do enormously better. Binary search works like finding a word in a dictionary: open to the middle. Is your target before or after this point? Throw away half the data and repeat. Each step halves what's left.

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // middle index
        if (arr[mid] == target) {
            return mid;                     // found
        } else if (arr[mid] < target) {
            low = mid + 1;                  // target is in the right half
        } else {
            high = mid - 1;                 // target is in the left half
        }
    }
    return -1;
}

Trace it: searching a sorted array of 1000 elements, linear search may take 1000 steps. Binary search takes at most ten (because 2¹⁰ > 1000). For a million elements, it's twenty steps versus a million. That's the magic of O(log n), and it's why sorted data is so valuable.

The catch and the trade-off

Binary search has one strict requirement: the data must be sorted. On unsorted data it gives wrong answers. So there's a trade-off worth understanding: if you search a dataset many times, it's worth sorting it once (an O(n log n) cost we'll learn next chapter) so that every later search is a lightning-fast O(log n). If you search only once, plain linear search may be simpler. Recognising this "pay once to sort, save on every search" trade-off is exactly the kind of reasoning interviews reward.

A subtle bug to avoid

Notice we wrote mid = low + (high - low) / 2 instead of the obvious (low + high) / 2. Why? For very large arrays, low + high can overflow the integer limit, producing a negative number and a crash. The subtraction form avoids it. This is a famous interview detail — the "binary search overflow bug" went undetected in real libraries for years. Mentioning it signals real depth.

The pattern beyond arrays

Binary search is more than an array trick — it's a way of thinking that appears everywhere: "binary search on the answer", searching in rotated arrays, finding boundaries. The core idea — repeatedly halving a search space using a yes/no question — is one of the most reused patterns in competitive programming and interviews.

// The shape of every binary search:
// 1. Define a range [low, high]
// 2. Ask a question at the middle
// 3. Discard the half that can't contain the answer
// 4. Repeat until the range is empty

Master this shape and a whole class of problems opens up. Next we tackle sorting — the operation that makes binary search possible, and a rich source of interview questions in its own right.