medium

Find First and Last Position of Element in Sorted Array

Find the first and last index of a target value in a sorted array.

1. Define the problem

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. Run a boundary search twice — once for the first index not smaller than target, and once for the first index not smaller than target + 1 — to pin down both ends of the run.

Constraints

  • 0 ≤ nums.length ≤ 105
  • -109 ≤ numsi ≤ 109
  • nums is a non-decreasing array
  • -109 ≤ target ≤ 109

Example

Inputnums = [5, 7, 7, 8, 8, 10], target = 8
Output[3, 4]

Explanation The value 8 first appears at index 3 and last appears at index 4.

2. Know the words first

In plain terms

Boundary search
A binary search that looks for the first index where a condition flips from false to true, instead of an exact value match.
3. Visualize the solution

Two boundary searches pin down the start and end of the run

Two boundary searches pin down the start and end of the run
Statusleft-search

Searching for the first index ≥ 8: mid=2 (value 7), 7 < 8, so low moves right.

What happens in this step

low=0, high=5
mid = 0 + floor((5-0)/2) = 2, nums[2] = 7

7 < 8, so index 2 cannot be the first index ≥ 8 — the boundary is somewhere to the right. low becomes 3.
Step 1 of 4

Steps to visualize

  1. Binary search for the first index whose value is not smaller than target — that is the left edge.
  2. If that index is out of range or does not hold target, the value is absent — return [-1, -1].
  3. Binary search again for the first index whose value is not smaller than target + 1.
  4. One step back from that second search is the right edge of the run.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Two boundary searches pin down the start and end of the run
Statusleft-search

Searching for the first index ≥ 8: mid=2 (value 7), 7 < 8, so low moves right.

What happens in this step

low=0, high=5
mid = 0 + floor((5-0)/2) = 2, nums[2] = 7

7 < 8, so index 2 cannot be the first index ≥ 8 — the boundary is somewhere to the right. low becomes 3.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function searchRange(nums, target) {
  function lowerBound(value) {
    let low = 0;
    let high = nums.length;

    while (low < high) {
      const mid = low + Math.floor((high - low) / 2);
      if (nums[mid] < value) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    return low;
  }

  const left = lowerBound(target);
  if (left >= nums.length || nums[left] !== target) {
    return [-1, -1];
  }

  const right = lowerBound(target + 1) - 1;
  return [left, right];
}
Time
O(log n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [5, 7, 7, 8, 8, 10], target = 8[3, 4]example from the docstring
nums = [5, 7, 7, 8, 8, 10], target = 6[-1, -1]target value absent from the array
nums = [], target = 0[-1, -1]empty array, nothing to find
nums = [5], target = 5[0, 0]smallest valid input, target present
nums = [5], target = 3[-1, -1]smallest valid input, target absent
nums = [2, 2, 2, 2], target = 2[0, 3]every element equals the target
nums = [1, 3, 3, 5, 7, 7, 7], target = 7[4, 6]the matching run sits at the end of the array

Keep reading