Offensive Security Researcher & Quantum Cryptography Analyst

Binary Search Algorithm: Working, Explanation, and Efficient Search Technique

Abdul Wahab Junaid
Binary search algorithm and working of this algorithm

I consider binary search one of the most elegant algorithms I have ever learned, precisely because of how much power it draws from a single assumption: that the data I am searching is sorted. Instead of checking elements one at a time, binary search repeatedly cuts the search space in half, comparing my target value against the middle element and discarding the half of the array that cannot possibly contain it. This gives me logarithmic-time search, a dramatic improvement over linear search, and it is a technique whose underlying idea — eliminating half the possibilities with each step — shows up again and again across computer science, well beyond just searching arrays.

History and Background

The earliest known reference to a binary search-like procedure dates back to 1946, when John Mauchly discussed the technique in a lecture as part of the Moore School Lectures on computing, one of the first formal courses on computer design and programming. The algorithm was formally published in 1962 by D.H. Lehmer, though correct implementations remained surprisingly elusive for decades — famously, Jon Bentley noted in his 1986 book Programming Pearls that most professional programmers’ implementations of binary search contained bugs, and it took until 1962 for the first published bug-free version to appear, with an integer overflow bug in the standard midpoint calculation persisting undetected in many textbooks and libraries (including Java’s own standard library) until it was identified and fixed in 2006.

Problem Statement

I need an efficient way to determine whether a target value exists within a large sorted collection, and if so, to find its position, without having to check every single element. Binary search solves this by exploiting the sorted order of the data: I can immediately rule out half of the remaining search space with a single comparison, giving me O(log n) time complexity instead of the O(n) required by a naive linear scan.

Core Concepts

How It Works

I follow these steps to search for a target value:

  1. I set low to the first index and high to the last index of the array.
  2. While low is less than or equal to high, I compute the midpoint index.
  3. I compare the value at the midpoint with my target: if they are equal, I have found the target and return its index.
  4. If the target is smaller than the midpoint value, I discard the right half by setting high to mid - 1.
  5. If the target is larger, I discard the left half by setting low to mid + 1.
  6. I repeat this process until I find the target or the search space becomes empty (low exceeds high), in which case the target does not exist in the array.

Working Principle

The mechanism I rely on is that sorted order lets a single comparison eliminate an entire half of the remaining possibilities. Because the array is sorted, if my target is less than the middle element, I know with certainty it cannot exist anywhere to the right of the middle — every element there is guaranteed to be even larger. This certainty is what allows binary search to discard half the search space with just one comparison, rather than needing to check each discarded element individually. Repeating this halving process rapidly narrows the search space down to a single element or confirms the target’s absence.

Mathematical Foundation

If I start with n elements, after one comparison the search space shrinks to at most n/2 elements. After k comparisons, the search space size is:

$$\frac{n}{2^k}$$

The algorithm terminates when the search space shrinks to at most 1 element, so I solve for k:

$$\frac{n}{2^k} \leq 1 \implies 2^k \geq n \implies k \geq \log_2 n$$

This gives the time complexity:

$$T(n) = O(\log n)$$

This recurrence can also be expressed directly as:

$$T(n) = T\left(\frac{n}{2}\right) + O(1)$$

which, by the Master Theorem (with $a=1$, $b=2$, $f(n)=O(1)$), resolves to $T(n) = O(\log n)$.

Diagrams

flowchart TD
    A["Start: low = 0, high = n - 1"] --> B{"Is low ≤ high?"}
    B -- Yes --> D["mid = low + (high - low) / 2"]
    B -- No --> C["Target not found"]

    D --> E{"Is A[mid] = target?"}
    E -- Yes --> F["Return mid (Target Found)"]
    E -- No --> G{"Is A[mid] < target?"}

    G -- Yes --> H["low = mid + 1"]
    G -- No --> I["high = mid - 1"]

    H --> B
    I --> B

graph LR
    A["[2,4,6,8,10,12,14] target=10"] --> B["mid=8, 8<10, search right"]
    B --> C["[10,12,14] mid=12, 12>10, search left"]
    C --> D["[10] mid=10, found!"]

Pseudocode

BINARY-SEARCH(A, target)
    low = 0
    high = length(A) - 1

    while low <= high
        mid = low + (high - low) / 2
        if A[mid] == target
            return mid
        else if A[mid] < target
            low = mid + 1
        else
            high = mid - 1

    return -1  // target not found

Step-by-Step Example

I will search for the target value 10 in the sorted array [2, 4, 6, 8, 10, 12, 14] (indices 0–6).

Step 1: low=0, high=6. mid = 0 + (6-0)/2 = 3. A[3] = 8. 8 < 10, so I discard the left half: low = 4.

Step 2: low=4, high=6. mid = 4 + (6-4)/2 = 5. A[5] = 12. 12 > 10, so I discard the right half: high = 4.

Step 3: low=4, high=4. mid = 4 + (4-4)/2 = 4. A[4] = 10. Match found! Return index 4.

Result: Target 10 found at index 4, after only 3 comparisons instead of up to 7 with a linear scan.

Time Complexity

Space Complexity

The iterative version of binary search requires only O(1) additional space, since it just tracks low, high, and mid as simple variables. The recursive version requires O(log n) space due to the call stack, since each recursive call represents one level of the halving process. I generally prefer the iterative version in performance-sensitive code specifically to avoid this recursion overhead.

Correctness Analysis

I prove binary search correct using a loop invariant: at the start of every iteration, if the target exists in the array, it must lie within the current range A[low..high]. This holds trivially at the start, since the initial range covers the entire array. During each iteration, I compare the target to the midpoint value: if they match, I have found it and can return immediately; if the target is smaller, sortedness guarantees it cannot exist in A[mid+1..high], so narrowing the range to A[low..mid-1] preserves the invariant; symmetric reasoning applies if the target is larger. Since the search space strictly shrinks by at least one element with every iteration, the loop is guaranteed to terminate, and when it does — either by finding a match or by low exceeding high — the invariant guarantees the result is correct: either the target has been found, or it provably does not exist anywhere in the original array.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

// Iterative binary search implementation
int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;  // avoids 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() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;

    int result = binarySearch(arr, n, target);

    if (result != -1) {
        printf("Target %d found at index %d\n", target, result);
    } else {
        printf("Target %d not found in array\n", target);
    }

    return 0;
}

Sample Input and Output

Input: Sorted array [2, 4, 6, 8, 10, 12, 14], target = 10

Output: Target 10 found at index 4

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version