Skip to main content

24. Find First and Last Position of Element in Sorted Array

mediumAsked at Booking

Locate the exact date range of a target value in a sorted list — Booking applies binary search to find the first and last available nights when a property's rate matches a target price tier.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers nums sorted in non-decreasing order and a target, find the starting and ending position of the target value in the array. Return [-1, -1] if the target is not found. Your solution must run in O(log n) time.

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is a non-decreasing array
  • -10^9 <= target <= 10^9

Examples

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]

Example 3

Input
nums = [], target = 0
Output
[-1,-1]

Approaches

1. Linear scan

Scan from both ends to find first and last occurrence.

Time
O(n)
Space
O(1)
function searchRange(nums, target) {
  let first = -1, last = -1;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      if (first === -1) first = i;
      last = i;
    }
  }
  return [first, last];
}

Tradeoff:

2. Two binary searches (left and right bound)

Run binary search twice — once biased left (first occurrence) and once biased right (last occurrence). O(log n).

Time
O(log n)
Space
O(1)
function searchRange(nums, target) {
  function bound(isLeft) {
    let lo = 0, hi = nums.length - 1, idx = -1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (nums[mid] === target) {
        idx = mid;
        if (isLeft) hi = mid - 1;
        else lo = mid + 1;
      } else if (nums[mid] < target) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return idx;
  }

  return [bound(true), bound(false)];
}

Tradeoff:

Booking-specific tips

Booking wants O(log n) from the start — mention the constraint before coding. The key insight to communicate: the two searches are identical except for which side you continue on when you hit the target.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find First and Last Position of Element in Sorted Array and other Booking interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →