Find First and Last Position of Element in Sorted Array

Medium

binary-searcharray

Given a non-decreasing integer array nums and a target, return the first and last index of target. If it is absent, return -1 -1. Must run in O(log n).

Input

Line 1: space-separated integers (sorted, may repeat)
Line 2: integer target

Output: two indices, space-separated.

Example 1

Input:

5 7 7 8 8 10
8

Output:

3 4

Example 2

Input:

5 7 7 8 8 10
6

Output:

-1 -1

Constraints

0 ≤ nums.length ≤ 10^5
Sorted non-decreasing.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Find First and Last Position of Element in Sorted Array

Medium

binary-searcharray

Given a non-decreasing integer array nums and a target, return the first and last index of target. If it is absent, return -1 -1. Must run in O(log n).

Input

Line 1: space-separated integers (sorted, may repeat)
Line 2: integer target

Output: two indices, space-separated.

Example 1

Input:

5 7 7 8 8 10
8

Output:

3 4

Example 2

Input:

5 7 7 8 8 10
6

Output:

-1 -1

Constraints

0 ≤ nums.length ≤ 10^5
Sorted non-decreasing.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.