Topics › Binary Search › BS on 1D Arrays

First and last occurrence

Easy TUF ID 85 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array arr sorted in non-decreasing order and an integer x. Return the index of the first occurrence of x and the index of the last occurrence of x as a pair {first, last}. If x does not appear, return {-1, -1}. The required running time is O(log n).

Constraints: 0 ≤ n ≤ 10^5, values and x fit in a 32-bit signed integer. Duplicates are the whole point of the problem.

Example 1

arr = [5, 7, 7, 8, 8, 10], x = 8
answer = [3, 4]           // 8 occupies indices 3 and 4

Example 2

arr = [5, 7, 7, 8, 8, 10], x = 6
answer = [-1, -1]         // 6 is not present

Example 3

arr = [2, 2, 2, 2], x = 2
answer = [0, 3]           // the whole array is one run of x

Approach 1: Brute force, linear scan

Intuition. Scan once. The first time we see x, record the index as first. Every time we see x, overwrite last, so it ends up at the final copy. If first is never set, x is absent and last was never set either.

Algorithm.

1. first = -1, last = -1.
2. For each index i: if arr[i] == x, set first = i if it is still -1, and set last = i.
3. Return {first, last}.

static int[] bruteForce(int[] arr, int x) {
    int first = -1, last = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == x) {
            if (first == -1) first = i;   // only the first hit sets this
            last = i;                     // every hit moves this forward
        }
    }
    return new int[]{first, last};
}

Complexity. Time O(n), space O(1). Fine for one query, too slow when the array is long and queried repeatedly, and not what the problem asks for.

Approach 2: Optimal, lower bound and upper bound

Intuition. Two standard binary searches describe the run of x completely:

• the lower bound lb is the first index with arr[i] >= x;
• the upper bound ub is the first index with arr[i] > x.

If x is present, all its copies sit in the index range [lb, ub - 1]: lb is the first copy (everything before it is < x), and ub - 1 is the last copy (everything from ub onward is > x). If x is absent, then lb == ub and arr[lb] is either out of range or a different value; either way we detect absence by checking lb == n || arr[lb] != x.

Algorithm.

1. first = lowerBound(arr, x).
2. If first == n or arr[first] != x, return {-1, -1}.
3. last = upperBound(arr, x) - 1.
4. Return {first, last}.

static int[] optimalBounds(int[] arr, int x) {
    int n = arr.length;
    int first = lowerBound(arr, x);
    if (first == n || arr[first] != x) return new int[]{-1, -1};   // x is not in the array at all
    int last = upperBound(arr, x) - 1;
    return new int[]{first, last};
}

private static int lowerBound(int[] arr, int x) {     // first index with arr[i] >= x, or n
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private static int upperBound(int[] arr, int x) {     // first index with arr[i] > x, or n
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Dry run on arr = [5, 7, 7, 8, 8, 10], x = 8. Lower bound (predicate arr[mid] >= 8), half-open range [lo, hi):

arr[3] == 8, so x is present. Upper bound (predicate arr[mid] > 8):

last = ub - 1 = 4, answer {3, 4}.

Complexity. Time O(log n): two binary searches. Space O(1).

The attraction of this approach is reuse: lower and upper bound are general tools, and once you trust them this problem needs no new reasoning.

Approach 3: Optimal, two purpose-built binary searches

Intuition. Instead of bounds that work with >= and >, write a search that only cares about equality. To find the first occurrence: run a normal binary search, but when arr[mid] == x, do not stop; remember mid and keep searching the left half, because an earlier copy may exist. To find the last occurrence, mirror it: on a hit, remember mid and search the right half. The < and > cases move the pointers exactly as in ordinary binary search.

This version is the one usually taught first because it is a one-line change from the basic search, and it returns -1 by itself when x is absent.

Algorithm.

1. firstOccurrence: lo = 0, hi = n - 1, ans = -1. While lo <= hi: if arr[mid] == x, set ans = mid, hi = mid - 1; else if arr[mid] < x, lo = mid + 1; else hi = mid - 1.
2. If that returned -1, answer {-1, -1}.
3. lastOccurrence: same, but on a hit set ans = mid, lo = mid + 1.
4. Return {first, last}.

static int[] optimalDirect(int[] arr, int x) {
    int first = firstOccurrence(arr, x);
    if (first == -1) return new int[]{-1, -1};
    return new int[]{first, lastOccurrence(arr, x)};
}

private static int firstOccurrence(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) {
            ans = mid;            // found one; an earlier copy may still exist on the left
            hi = mid - 1;
        } else if (arr[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

private static int lastOccurrence(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) {
            ans = mid;            // found one; a later copy may still exist on the right
            lo = mid + 1;
        } else if (arr[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

Complexity. Time O(log n), space O(1).

Why does continuing after a hit not break the search? After arr[mid] == x we set hi = mid - 1 (for the first occurrence). Everything we discard, [mid, hi], is >= x, so no earlier copy of x is lost, and ans already holds a valid copy in case the left half has none. The loop therefore always ends with ans equal to the leftmost copy it could prove exists, which is the leftmost copy overall.

Edge cases and pitfalls

• Absent x. Both optimal approaches must return {-1, -1}, including when x is smaller or larger than everything. In Approach 2 the first == n check prevents an out-of-bounds read of arr[n].
• Empty array. {-1, -1}. Approach 2: lb = 0 == n. Approach 3: hi = -1, loop skipped, ans = -1.
• Single copy. first == last; the test x = 5 and x = 10 on the example array checks the ends of the array.
• Whole array equal to x. {0, n - 1}; the upper bound is n, so last = n - 1 is still a valid index.
• Stopping at the first hit. The classic bug: returning mid as soon as arr[mid] == x gives some occurrence, not the first or last. Always keep searching in the correct direction.
• Off-by-one on last. The upper bound points past the last copy, so subtract one. Forgetting this returns an index holding a value > x (or n).
• Overflow in mid. Use lo + (hi - lo) / 2.

Related problems

• Lower Bound and Upper Bound are the two building blocks of Approach 2.
• Count Occurrences in a Sorted Array is last - first + 1, so it follows directly from this one.
• Search X in sorted array is the basic search that Approach 3 modifies.