0%

leetcode34在排序数组查找元素第一和最后位置

题目地址

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目描述

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:
输入:nums = [], target = 0
输出:[-1,-1]

提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
```

## 代码实现
```
javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let len = nums.length, left = 0, right = len - 1;
let start = -1, end = -1;
while (left <= right) {
let mid = Math.floor((left + right)/2);
if (nums[mid] === target) {
start = mid;
end = mid;
while(--start >= 0 && nums[start] === target) {

}
start++;
while(++end < len && nums[end] === target) {

}
end--;
return [start, end];
}else if (nums[mid] < target) {
left = mid + 1;
}else {
right = mid - 1;
}
}
return [start, end];
};

代码优化

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
27
28
29
30
31
32
33
34
35
var searchRange = function(nums, target) {
let right = nums.length - 1, left = 0;
// 定义获得最左边目标值的函数
function getLeft(left, right) {
while (left <= right) {
let mid = Math.floor((left + right)/2);
if (nums[mid] === target) {
right = mid - 1;
}else if (nums[mid] < target) {
left = mid + 1;
}else {
right = mid - 1;
}
}
if (left >= nums.length || nums[left] !== target) return -1;
return left;
}
// 定义获得最右边目标值的函数
function getRight(left, right) {
while (left <= right) {
let mid = Math.floor((left + right)/2);
if (nums[mid] === target) {
left = mid + 1;
}else if (nums[mid] < target) {
left = mid + 1;
}else {
right = mid - 1;
}
}
if (right < 0 || nums[right] !== target) return -1;
return right;
}

return [getLeft(left,right), getRight(left, right)];
};