DSA · Binary Search · #70
Find First and Last Position of Element in Sorted Array
Module 59 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value. Implement `searchRange(nums, target)` that returns `[first, last]` — the indices of the first and last occurrence of `target`. If `target` is not found, return `[-1, -1]`. You must write an algorithm with `O(log n)` runtime complexity.
Examples
nums = [5,7,7,8,8,10], target = 8→[3,4]— 8 appears at indices 3 and 4.nums = [5,7,7,8,8,10], target = 6→[-1,-1]— 6 is not present.nums = [], target = 0→[-1,-1]
Constraints
- · 0 <= nums.length <= 10^5
- · -10^9 <= nums[i] <= 10^9
- · nums is sorted in non-decreasing order
- · -10^9 <= target <= 10^9
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.