Linear & Binary Search

Searching means finding whether (and where) a target value exists in a collection. There are two fundamentally different strategies depending on one thing: is the data sorted? If not, you have no choice but to check every element. If it is sorted, you can throw away half the remaining data with every single comparison. That difference — O(n) versus O(log n) — is one of the most consequential ideas in this entire track, and it's the reason so many algorithms bother sorting data before working with it.

Linear Search — O(n)

Linear search makes no assumptions about the data. It simply walks through the array from the start, comparing each element to the target, and stops the moment it finds a match.

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;      // found — return its index
        }
    }
    return -1;             // not found anywhere
}

Time complexity: O(n) worst case and average case — a target near the end (or absent) forces scanning nearly the whole array. Best case is O(1) if the target is at index 0. Space complexity: O(1) — only a loop index is used.

Binary Search — O(log n) — Requires a Sorted Array

Binary search works by repeatedly checking the middle element of the current search range. If it matches, you're done. If the middle element is smaller than the target, the target (if present) must be somewhere to the right, so the entire left half — including the middle — is discarded. If it's larger, the right half is discarded. Each comparison halves the search space.

Iterative Binary Search

public static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;   // avoids overflow vs (low + high) / 2
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;             // discard left half, including mid
        } else {
            high = mid - 1;            // discard right half, including mid
        }
    }
    return -1;                         // low > high means the range is empty — not found
}

Time complexity: O(log n) — the search range is halved on every iteration, so it takes about log₂(n) comparisons to shrink to nothing. Space complexity: O(1) — just three integer variables, no matter how large the array.

Recursive Binary Search

public static int binarySearchRecursive(int[] arr, int target, int low, int high) {
    if (low > high) {
        return -1;                     // empty range — target isn't present
    }
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, high);
    } else {
        return binarySearchRecursive(arr, target, low, mid - 1);
    }
}

Time complexity: O(log n) — same halving argument as the iterative version. Space complexity: O(log n) — each recursive call adds a frame to the call stack, and there are about log₂(n) nested calls before the base case is hit.

Off-By-One Bugs to Watch For

Worked Variant: First and Last Occurrence With Duplicates

Plain binary search stops at the first match it happens to land on, which is useless if the array has duplicates and you need the first or last index of the target. The fix: don't stop at the first match — record it, then keep narrowing in the direction that could reveal an earlier (or later) occurrence.

public static int firstOccurrence(int[] arr, int target) {
    int low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;      // keep searching the left half for an earlier match
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

public static int lastOccurrence(int[] arr, int target) {
    int low = 0, high = arr.length - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;       // keep searching the right half for a later match
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

Trace firstOccurrence on [2, 4, 4, 4, 4, 8, 10] for target 4: mid=3 (value 4) matches — record result=3, then search [2,4,4] (indices 0-2) for an earlier one. mid=1 (value 4) matches — record result=1, search [2] (index 0). arr[0]=2 < 4, so low moves past high and the loop ends. Final answer: index 1, the first occurrence.

Time complexity: O(log n) for each function — it's still one binary search, just one that keeps narrowing after a match instead of stopping. Space complexity: O(1) — only a few integer variables.