DSA Complexity

Binary search cost

Autocomplete needs the first catalog index not less than a prefix. At n = 10^7, a linear scan per keystroke is a product bug.

Binary search pays by a candidate interval. The complexity claim assumes sorted (or monotone) evidence and O(1) random access.

Algorithm journey

State the interval

Closed or half-open; pick one.

Probe mid

Safe midpoint arithmetic.

Discard a half

Only when the predicate proves it impossible.

Collapse to answer

Exact hit, lower bound, or empty.

What actually happens

Naive idea: scan. Correct, Theta(n) per query.

Better idea: halve. Theta(log n) per query on sorted random-access data.

It fails on unsorted input, linked lists (midpoint is linear), and when you sort only for one query (Theta(n log n) preprocessing can lose to one scan).

Invariant

If an answer exists, it remains inside the candidate interval after every update; the interval shrinks strictly.

How to choose binary search (cost view)

1. Is data already ordered or worth ordering for many queries? Then log n probes win.

2. Single query on unsorted data? Linear scan can beat sort + binary.

3. Need lower/upper bound among duplicates? Budget the same Theta(log n) class with a careful loop.

Quantitative check

log2(10^7) ≈ 23. One hundred ordered lookups ≈ 2,300 comparisons vs up to 10^9 for naive scans.

How it works

Find Middle

Calculate the middle index of the current search range.

Compare

Compare the middle element with the target:
• Equal: Found it!
• Smaller: Search the right half.
• Larger: Search the left half.

Repeat

Repeat until the element is found or the search range is empty.

🎮 Interactive Binary Search Demo

Enter a number to search for. The array is already sorted. Watch how half the elements are eliminated at each step!

ℹ️ Ready to Binary Search!

103

404

505

606

707

808

909

Tip: Sorted Data Only!

Binary Search ONLY works on sorted lists. If your data is unsorted, you must sort it first (which takes O(n log n)) or use Linear Search. It's perfect for static data that doesn't change often but is searched frequently.

Interactive boundary-contract lab

Exact-match search is only one binary-search contract. Step through lower bound, upper bound, and a monotone feasibility predicate using the safer half-open interval [lo, hi).

Binary-search contract laboratory

Search for the first true boundary

target

Step 1 of 5

Evaluate index 4

[lo, hi) = [0, 8)

i=0

false

i=1

true

i=2

true

i=3

true

i=4

true

i=5

true

i=6

true

i=7

true

Predicate

data[i] ≥ 2 · first occurrence or insertion point

Decision

Predicate is true at 4; the first true position is at 4 or earlier, so set hi = 4.

Invariant

All indices below lo are proved false; all indices at or above hi are proved true. The answer remains in [lo, hi].

Use ← →, Home, or End after focusing the lab.

💻 Implementation

Python

python

def binary_search(arr, target):
    """
    Searches for target in a sorted array arr.
    Returns index if found, else -1.
    """
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
            
        # If target is greater, ignore left half
        elif arr[mid] < target:
            left = mid + 1
            
        # If target is smaller, ignore right half
        else:
            right = mid - 1
            
    # If we reach here, then the element was not present
    return -1

def lower_bound(arr, target):
    """First index i with arr[i] >= target; len(arr) if none."""
    left, right = 0, len(arr)  # half-open [left, right)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    """First index i with arr[i] > target; len(arr) if none."""
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Example Usage
sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = binary_search(sorted_list, target)

if result != -1:
    print(f"Element found at index: {result}")
else:
    print("Element not found")

Java

java

public class BinarySearch {
    /**
     * Binary Search - Divide and conquer search algorithm
     * 
     * Time Complexity:
     * - Best Case: O(1) - element at middle
     * - Average Case: O(log n)
     * - Worst Case: O(log n)
     * 
     * Space Complexity: O(1) - iterative version
     * 
     * IMPORTANT: Array must be sorted!
     */
    
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // Calculate mid (avoids overflow)
            int mid = left + (right - left) / 2;
            
            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid;
            }
            
            // If target is greater, ignore left half
            if (arr[mid] < target) {
                left = mid + 1;
            }
            // If target is smaller, ignore right half
            else {
                right = mid - 1;
            }
        }
        
        // If we reach here, element was not present
        return -1;
    }

    /** First index i with arr[i] >= target, or arr.length. */
    public static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    /** First index i with arr[i] > target, or arr.length. */
    public static int upperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] sortedList = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        
        int result = binarySearch(sortedList, target);
        
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found");
        }
    }
}

One invariant, several useful APIs

Binary search contracts and postconditions
Contract	Predicate at index i	Postcondition	Duplicates
Exact match	`a[i] == x`	Any matching index, otherwise −1	No promise which equal element
Lower bound	`a[i] >= x`	First true index in `[0,n]`	First occurrence when x exists
Upper bound	`a[i] > x`	First index after all values ≤ x	One past the final occurrence
Equal range	lower + upper	`[lowerBound(x), upperBound(x))`	Count is upper − lower

Half-open invariant: indices below left are proved false, indices at or above right are proved true, and the boundary remains in [left,right]. Each iteration strictly shrinks right-left, proving termination.

Binary search on the answer

Define a monotone predicate

For candidate x, feasible(x) changes direction at most once: false…false, true…true.

Prove the direction

Capacity, time, or budget increases often make feasibility easier; minimum feasible is first true.

Bound the domain

Choose known false/true sentinels or grow a bound exponentially. The answer-domain width contributes the log factor.

If one feasibility check costs T, searching an integer domain of width W costs O(T log W), not O(log n). Typical questions ask for minimum capacity, maximum tolerable distance, earliest completion time, or a partition limit.

Correctness, testing, and production contracts

Proof sketch

Initialization places the boundary inside the candidate interval.
The midpoint predicate discards only a region proved unable to contain the first true index.
The interval length decreases every iteration, so it reaches zero.
At termination, everything below left is false and everything from it onward is true.

Boundary test matrix

• Empty and singleton arrays; target before first and after last.
• All-equal and duplicate-heavy arrays; verify lower/upper postconditions.
• Integer extremes; compute midpoint as lo + (hi-lo)/2.
• Cross-check lower bound with a linear oracle on randomized sorted inputs.
• For predicates, test all-false, all-true, and transitions at both endpoints.

API rule: document sortedness, comparator/order, duplicate semantics, and the miss sentinel. On linked lists, midpoint access destroys the logarithmic benefit; arrays and random-access indexes are the intended substrate.

⚡ Complexity Analysis

Time Complexity

✓
O(1) - Best Case
Target is the middle element
✓
O(log n) - Worst Case
Logarithmic time (very fast)

Space Complexity

✓
O(1)
Iterative implementation

✅ Pros & ❌ Cons

✅ Advantages

✓Extremely fast for large datasets (O(log n))
✓Efficient comparisons

❌ Disadvantages

✗Requires the array to be sorted
✗Harder to implement correctly (off-by-one errors)
✗Only works on data structures with random access (arrays)

Exercises

Why is "O(log n) on a linked list" usually a lie for classic binary search?
Quantify sort-once + q binary searches vs q linear scans for n=10^6, q=10.
Give a duplicate array where "any index" vs lower bound change the returned index but not the Theta(log n) class.

Primary sources

Cormen et al., CLRS: binary search and loop invariants.
Bentley, Programming Pearls: binary search lessons.
C++ std::lower_bound complexity notes.

Short takeaway

Binary Search = Divide and conquer on sorted data.Time: O(log n).Space: O(1).Use when: List is sorted and large.