Search for a Range in a Sorted Array

Given a sorted array that may contain duplicates, return the indices of the first and last occurrence of target, or null if it is not present. The solution should run in O(log n).

LeetCode: 34. Find First and Last Position of Element in Sorted Array

Example

Text

Input:  [1, 3, 5, 5, 5, 5, 28, 37, 42], target = 5    Output: [2, 5]
Input:  [1, 3, 5, 5, 5, 5, 28, 37, 42], target = 4    Output: null

Brute force: linear scan

Java

import java.util.Arrays;

public class Main {
    // Returns {first, last} or null when the target is absent.
    static int[] searchRange(int[] nums, int target) {
        int first = -1;
        int last = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return first == -1 ? null : new int[] {first, last};
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 5, 5, 5, 28, 37, 42};
        System.out.println(Arrays.toString(searchRange(nums, 5)) + " " + Arrays.toString(searchRange(nums, 4)));
    }
}

Output

[2, 5] null

Time: O(n). If target fills most of the array, even scanning outwards from one binary-search hit is O(n). Space: O(1).

Optimal: two lower bounds

lowerBound(x) is the first index whose value is >= x. It is a binary search for the boundary between "less than x" and "at least x":

The first occurrence of target is lowerBound(target), if the value there equals target.
The last occurrence is lowerBound(target + 1) - 1: the index right before the first value greater than target.

Java

import java.util.Arrays;

public class Main {
    static int lowerBound(int[] nums, long x) {
        int lo = 0;
        int hi = nums.length; // the answer is in lo..hi, both inclusive
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < x) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    // Returns {first, last} or null when the target is absent.
    static int[] searchRange(int[] nums, int target) {
        int first = lowerBound(nums, target);
        if (first == nums.length || nums[first] != target) {
            return null;
        }
        int last = lowerBound(nums, (long) target + 1) - 1;
        return new int[] {first, last};
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 5, 5, 5, 28, 37, 42};
        System.out.println(Arrays.toString(searchRange(nums, 5)) + " " + Arrays.toString(searchRange(nums, 4)));
        System.out.println(Arrays.toString(searchRange(nums, 42)) + " " + Arrays.toString(searchRange(new int[] {}, 1)));
        System.out.println(Arrays.toString(searchRange(new int[] {Integer.MAX_VALUE, Integer.MAX_VALUE}, Integer.MAX_VALUE)));
    }
}

Output

[2, 5] null
[8, 8] null
[0, 1]

Time: O(log n). Space: O(1).

The search compares in long so that target + 1 cannot overflow when target is Integer.MAX_VALUE. The last output line above shows that case. Arrays.toString prints a null array as null.

Java has no lowerBound for int[]. Arrays.binarySearch returns the index of some match, which is not guaranteed to be the first or last when there are duplicates. A single helper that takes the boundary test as an IntPredicate (a function from int to boolean) covers both searches. firstIndex returns the first index where the predicate becomes true:

Java

import java.util.Arrays;
import java.util.function.IntPredicate;

public class Main {
    // First index whose value satisfies the predicate, or nums.length if none does.
    // The predicate must be false for a prefix of the array and true for the rest.
    static int firstIndex(int[] nums, IntPredicate atOrAfter) {
        int lo = 0;
        int hi = nums.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (atOrAfter.test(nums[mid])) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    static int[] searchRange(int[] nums, int target) {
        int first = firstIndex(nums, x -> x >= target);
        int end = firstIndex(nums, x -> x > target); // one past the last occurrence
        return first < end ? new int[] {first, end - 1} : null;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 5, 5, 5, 28, 37, 42};
        System.out.println(Arrays.toString(searchRange(nums, 5)) + " " + Arrays.toString(searchRange(nums, 4)));
    }
}

Output

[2, 5] null

Edge cases

Empty array: null.
Target smaller or larger than every element: lowerBound returns 0 or n, and the check finds no match.
Every element equal to the target: (0, n - 1), still in O(log n).