Description
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
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: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109nums is a non-decreasing array.-109 <= target <= 109
Solutions
Solution 1: Binary Search
We can perform two binary searches to find the left boundary and the right boundary.
The time complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).
| class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l = bisect_left(nums, target)
r = bisect_left(nums, target + 1)
return [-1, -1] if l == r else [l, r - 1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public int[] searchRange(int[] nums, int target) {
int l = search(nums, target);
int r = search(nums, target + 1);
return l == r ? new int[] {-1, -1} : new int[] {l, r - 1};
}
private int search(int[] nums, int x) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
|
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin();
if (l == r) {
return {-1, -1};
}
return {l, r - 1};
}
};
|
| func searchRange(nums []int, target int) []int {
l := sort.SearchInts(nums, target)
r := sort.SearchInts(nums, target+1)
if l == r {
return []int{-1, -1}
}
return []int{l, r - 1}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | function searchRange(nums: number[], target: number): number[] {
const search = (x: number): number => {
let [left, right] = [0, nums.length];
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
const l = search(target);
const r = search(target + 1);
return l === r ? [-1, -1] : [l, r - 1];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | impl Solution {
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
let n = nums.len();
let search = |x| {
let mut left = 0;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] < x {
left = mid + 1;
} else {
right = mid;
}
}
left
};
let l = search(target);
let r = search(target + 1);
if l == r {
return vec![-1, -1];
}
vec![l as i32, (r - 1) as i32]
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | /**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
function search(x) {
let left = 0,
right = nums.length;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
const l = search(target);
const r = search(target + 1);
return l == r ? [-1, -1] : [l, r - 1];
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | public class Solution {
public int[] SearchRange(int[] nums, int target) {
int l = Search(nums, target);
int r = Search(nums, target + 1);
return l == r ? new int[] {-1, -1} : new int[] {l, r - 1};
}
private int Search(int[] nums, int x) {
int left = 0, right = nums.Length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function searchRange($nums, $target) {
$search = function ($x) use ($nums) {
$left = 0;
$right = count($nums);
while ($left < $right) {
$mid = intdiv($left + $right, 2);
if ($nums[$mid] >= $x) {
$right = $mid;
} else {
$left = $mid + 1;
}
}
return $left;
};
$l = $search($target);
$r = $search($target + 1);
return $l === $r ? [-1, -1] : [$l, $r - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
fun searchRange(nums: IntArray, target: Int): IntArray {
val left = this.search(nums, target)
val right = this.search(nums, target + 1)
return if (left == right) intArrayOf(-1, -1) else intArrayOf(left, right - 1)
}
private fun search(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size
while (left < right) {
val middle = (left + right) / 2
if (nums[middle] < target) {
left = middle + 1
} else {
right = middle
}
}
return left
}
}
|