Voyz's Studio.

LeetCode算法笔记--在排序数组中查找元素的第一个和最后一个位置

字数统计: 394阅读时长: 2 min
2020/12/11 Share

LeetCode算法笔记–Day38

34. Find First and Last Position of Element in Sorted Array

题目:

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

example
input: nums = [5,7,7,8,8,10], target = 8
output: [3,4]

Analyze:

方法一:二分法

题目要求算法时间复杂度必须是O(logn) 的级别,提示可以使用二分搜索的方法。

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
// 二分法模板:

//1.左闭右闭
let _left = 0,_right = Arr.length-1;

while(_left <= _right){
let _mid = _left + ((_left+_right) >> 1);
if(Arr[_mid] == target){
/* option here */
}else if(Arr[+_mid] < target){
_left = _mid + 1;
}else if(target < Arr[_mid]){
_right = _mid - 1;
}
}
// 返回所需index
return ?

//2.左闭右开
let _left = 0,_right = Arr.length;

while(_left < _right){
let _mid = _left + ((_left+_right) >> 1);
if(Arr[_mid] == target){
/* option here */
}else if(Arr[+_mid] < target){
_left = _mid + 1;
}else if(target < Arr[_mid]){
_right = _mid;
}
}
// 返回所需index
return ?

My Answer:

Runtime complexity : O(logn)
Space complexity : O(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
25
26
27
28
29
30
31
32
33
34
35
36
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
if(nums.length == 0) return [-1,-1];

let searchIndex = function(option){
// 左闭右开区间
let _left = 0,_right = nums.length;

while(_left < _right){
let _mid = _left + ((_right - _left) >> 1);
if(nums[_mid] == target){
if(option == 'left'){
// 向左缩小范围
_right = _mid;
}else{
// 向左缩小范围
_left = _mid + 1;
}
}else if(nums[_mid] > target){
_right = _mid;
}else if(nums[_mid] < target){
_left = _mid + 1;
}
};
return option == 'left' ? _left : _right-1;
}

let _min = searchIndex('left'),_max = searchIndex('right');

return _min <= _max ? [_min,_max] : [-1,-1]

};
CATALOG
  1. 1. LeetCode算法笔记–Day38
  2. 2. 34. Find First and Last Position of Element in Sorted Array
    1. 2.1. 题目:
    2. 2.2. Analyze:
      1. 2.2.1. 方法一:二分法
    3. 2.3. My Answer: