Find First and Last Position of Element in Sorted Array

mediumSave

ArrayBinary Search

Given an array of integers nums sorted in non-decreasing order and a target integer target, find the starting and ending position of a given target value in the array. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

Example 1

Input

Output

[3, 4]

Explanation. The target value 8 occurs at indices 3 and 4.

Example 2

Input

Output

[-1, -1]

Explanation. The target value 6 does not appear in the input array, thus the output is [-1, -1].

Example 3

Input

[
  [],
  0
]

Output

[-1, -1]

Explanation. The input array is empty, therefore, no target can be found.

Example 4

Input

[
  [
    2,
    2
  ],
  2
]

Output

[0, 1]

Explanation. The target value 2 occurs in all the indices of the array, from 0 to 1.

Follow-up: How would you adapt your solution if the input numbers were not sorted?

Constraints:

1. The number of elements in the array is between 1 and 10000. 2. The values of each element in the array range from -10^9 to 10^9. 3. The array `nums` is always sorted in non-decreasing order. 4. The value `target` will range from -10^9 to 10^9.

Views: 2