Problems/Binary Search/First and Last Occurrences of a Number
Binary Search
medium

First and Last Occurrences of a Number

Find the first and last position of a given target value within a sorted array. This problem tests your ability to efficiently search sorted data, a core skill for any software engineer.

arraybinary searchsorted arraysearchlogarithmic time

Problem Statement

Given a sorted array of integers in ascending order, locate the starting and ending indices of a specified target value. If the target value is absent from the array, return an array containing [-1, -1].

Example 1
Input: numbers = [2, 5, 7, 7, 7, 8, 10], target = 7
Output: [2, 4]
The target value 7 appears first at index 2 and last at index 4.
Example 2
Input: numbers = [1, 3, 5, 7, 9, 11], target = 2
Output: [-1, -1]
The target value 2 does not exist in the array, so we return [-1, -1].
Constraints
  • -The array is sorted in ascending order.
  • -The array can contain duplicate values.
  • -The array can be empty.
  • -The target value is an integer.

Brute Force Approach

Imagine you're searching for a specific book in a library shelf but you don't know if it's there. You'd start from the beginning, check each book one by one until you find the first instance, and keep going until you find the last. This is a linear search, checking each element. The time complexity is O(n) because, in the worst case, you might have to scan the entire array, and the space complexity is O(1) because you're only using a constant amount of extra space.

TimeO(n)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem