PPractick

The problem

A log-analysis tool stores event timestamps sorted, and many events can share a timestamp. To show "all events at 10:42:05", it needs the first and last positions of that timestamp in the array, in O(log n), because the logs have hundreds of millions of lines. A single binary search finds an occurrence but not necessarily the first or last. The fix is two boundary searches: one that keeps looking left after a match, and one that keeps looking right.

Example: [5, 7, 7, 8, 8, 10], target 8 → [3, 4].

Function signature

vector<int> searchRange(const vector<int>& nums, int target);  // {first, last}, or {-1, -1}

Test cases

Input (nums, target)	Output	Explanation
([5, 7, 7, 8, 8, 10], 8)	[3, 4]
([5, 7, 7, 8, 8, 10], 6)	[-1, -1]	Not present
([], 0)	[-1, -1]
([2, 2, 2], 2)	[0, 2]	The whole array
([1, 2, 3], 1)	[0, 0]	A single occurrence
([1, 2, 3], 3)	[2, 2]	At the end

(Confirm: the array is sorted non-decreasingly; O(log n) is required.)

How interviewers phrase it

• "Find the first and last position of an element in a sorted array" (LeetCode 34).
• Often followed by "count the occurrences" (S.No 108).

Clarifying questions to ask

1. Is the array sorted? Duplicates allowed?
2. What should be returned if the target is absent?
3. Is O(log n) required? (A linear scan from one found index could be O(n) with many duplicates.)

Follow-ups to expect

1. "Why not find one occurrence and expand left and right?"
2. "How does the first-occurrence search differ from normal binary search?"
3. "Can you express it with lower and upper bound?"
4. "Complexity?"

Related questions

• Single element in a Sorted Array Medium
• Find peak element Medium
• Kth element of 2 sorted arrays Medium
• Search X in sorted array Easy
• Lower Bound Easy
• Upper Bound Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in