Command Palette

Search for a command to run...

Hectal
Problem 11.3 · Binary SearchMedium

Find First and Last Position

PatternBinary Search on an Index

What it teaches: Two boundary searches: lower bound for the first copy, upper bound minus one for the last.

Practise it on judges as “Find First and Last Position of Element in Sorted Array”.

The problem

Given a sorted array (with duplicates), return [first, last] indexes of target, or [-1, -1] if absent. O(log n).

Example 1

Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Example 2

Input: nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

Constraints

  • 0 ≤ n ≤ 10⁵
  • Sorted non-decreasing

Pattern clues in the wording

  • → Sorted with duplicates, need the range of a value
  • → O(log n)

These clues point to Binary Search on an Index: In sorted data, check the middle and throw away the half that can't contain the answer.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{-1, -1};
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [5,7,7,8,8,10]
target = 8
[3,4]
2
nums = [5,7,7,8,8,10]
target = 6
[-1,-1]
3
nums = []
target = 0
[-1,-1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: two bound searches · O(log n)
1

Optimal: two bound searches

Time O(log n) Space O(1)

first = lowerBound(target). If first is n or nums[first] != target, return [-1, -1]. Otherwise last = upperBound(target) − 1.

Approach 1
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};
        int last = bound(nums, target, true) - 1;
        return new int[]{first, last};
    }

    // first index with nums[i] >= t (upper == false) or nums[i] > t (upper == true)
    private int bound(int[] nums, int t, boolean upper) {
        int lo = 0, hi = nums.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > t || (!upper && nums[mid] == t)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

Verdict: Two binary searches, no linear scan.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Empty array
  • Target appears once
  • Whole array is the target

Mistakes people make

  • Scanning from a found copy (O(n) worst case).
  • Not checking that the lower bound actually holds the target.

Interview

Follow-up questions

How do you count occurrences of x?