Voyz's Studio.

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

算法题 热题HOT100 二分法
字数统计: 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：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa