Find First and Last Position of Element

mediumBinary Search+20 XPTime limit 2s

The array is sorted in non-decreasing order and may contain repeats. Find the first and last index of target.

Input:

line 1: n
line 2: n sorted integers
line 3: target

Output: first last (0-based), or -1 -1 if target is not in the array.

Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i], target ≤ 10⁹. Aim for O(log n).

Think about it: run binary search twice — once for the first index with value ≥ target, once for the first index with value > target.

Sample input 1

6
5 7 7 8 8 10
8

Sample output 1

3 4

Sample input 2

6
5 7 7 8 8 10
6

Sample output 2

-1 -1

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…