Find First and Last Position of Element in Sorted Array

Medium Binary Search Bisect Original on LeetCode

Find First and Last Position of Element in Sorted Array is a medium binary search problem solved with the bisect pattern. The best approach, optimal (two bisects), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from find one, then expand up.

Problem

Given a sorted array and a target, return the first and last index of target as [first, last], or [-1, -1] if it is not present. The solution must be O(log n).

Examples

Example 1

Input: nums = [2, 4, 4, 4, 6, 9], target = 4
Output: [1, 3]

Example 2

Input: nums = [2, 4, 6], target = 5
Output: [-1, -1]

Constraints

0 <= nums.length <= 10^5, sorted non-decreasing.
O(log n).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Find one, then expand	`O(log n + k)`	`O(1)`
Optimal (two bisects)	`O(log n)`	`O(1)`

1Find one, then expand

TimeO(log n + k)k is the number of copies; with all equal values this is O(n).

SpaceO(1)

Binary search for any occurrence, then walk left and right to the ends of the run.

Binary search for target.
Expand while neighbours equal target.

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, at = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] == target) { at = mid; break; }
            if (nums[mid] < target) lo = mid + 1; else hi = mid - 1;
        }
        if (at == -1) return new int[] { -1, -1 };
        int l = at, r = at;
        while (l > 0 && nums[l - 1] == target) l--;
        while (r < nums.length - 1 && nums[r + 1] == target) r++;
        return new int[] { l, r };
    }
}

2Optimal (two bisects)

TimeO(log n)

SpaceO(1)

bisect_left gives the first index with a value >= target. If it is out of range or not equal to target, the target is absent. Otherwise bisect_right - 1 gives the last occurrence.

first = bisectLeft(target).
If first == n or nums[first] != target, return [-1, -1].
last = bisectRight(target) - 1.

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = bound(nums, target, false);
        if (first == nums.length || nums[first] != target) return new int[] { -1, -1 };
        return new int[] { first, bound(nums, target, true) - 1 };
    }

    // strict = false: first index with a[i] >= x; strict = true: first index with a[i] > x
    private int bound(int[] a, int x, boolean strict) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (strict ? a[mid] > x : a[mid] >= x) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
}

Edge cases to test

Empty array
Target missing
Every element equals the target

Hints

Hint 1

first = bisect_left(target); last = bisect_right(target) - 1.

FAQ

What is the best time complexity for Find First and Last Position of Element in Sorted Array?

Optimal (two bisects) runs in O(log n) time and O(1) extra space.

Which pattern does Find First and Last Position of Element in Sorted Array use?

It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.

Is there a brute force solution for Find First and Last Position of Element in Sorted Array?

Yes. Find one, then expand takes O(log n + k) time and O(1) space. Binary search for any occurrence, then walk left and right to the ends of the run.

Which edge cases should I test for Find First and Last Position of Element in Sorted Array?

Empty array; Target missing; Every element equals the target.