Katkat
Back

Find first and last occurrence in sorted array

Applied IntuitionSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to modify the standard binary search algorithm to achieve logarithmic time complexity when searching for the boundary indices of a target value in a sorted array.

Problem Statement

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Function Signature

def search_range(nums: List[int], target: int) -> List[int]:

Examples

Example 1: Input: nums = [5, 7, 7, 8, 8, 10], target = 8 Output: [3, 4] Explanation: The value 8 starts at index 3 and ends at index 4.

Example 2: Input: nums = [5, 7, 7, 8, 8, 10], target = 6 Output: [-1, -1] Explanation: The value 6 is not in the array.

Constraints

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

Edge Cases

  • Empty array.
  • Array with a single element.
  • Array where the target is not present.
  • Array where all elements are the same as the target.

Hints

Hint 1

Since the array is sorted, consider using binary search, but remember that the target may appear multiple times.

Hint 2

To find the first occurrence, when you find the target, don't stop; continue searching in the left half of the array to see if an earlier occurrence exists.

Hint 3

Perform two separate binary searches: one to find the leftmost index where `nums[i] == target` and one to find the rightmost index.

Follow-up questions

  • How would you modify your approach if the array was rotated (e.g., [4, 5, 6, 0, 1, 2, 3])?
  • What is the space complexity of your solution, and can you optimize it if it is not O(1)?
  • How would you handle finding the first and last position if the array was sorted but included duplicate ranges across a much larger, distributed system?