关于前端:ARTS1A-Leetcode-34-题-在已排序的列表中查找目标数字的起止坐标

题目链接：

Find First and Last Position of Element in Sorted Array

题目的粗心就是给定一个升序的整形数组 nums 和一个指标数字 target ，要求返回一个数组，数组第一项是 target 在 nums 中第一次呈现的下标，第二项是 target 在 nums 最初一次呈现的下标。并且要求工夫复杂度为 O(log n)。

思路

读完题目就能够判断出这道算法题考的查问算法，要求工夫复杂度为 O(log n)，间接遍历必定是不行了，因而考查的二分查找算法，刚好工夫复杂度是 O(log n)。

我的思路是先通过二分查找算法，在 nums 中找到任意一个 target 呈现的下标，因为数组是升序的，找到一个下标后，别离向左右找到第一个和 target 不等的地位，就能够找出整个范畴。

解题

实现如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const len = nums.length;

    const i = binSearch(nums, 0, len - 1, target);

    if (i == -1) {
        return [-1, -1]
    }

    // 找到指标后，前后匹配，找出整个范畴
    const ret = [i, i];

    let x = i;
    while (x >= 0 && nums[x] == target) {
        ret[0] = x;
        x--;
    }

    x = i;
    while (x < len && nums[x] == target) {
        ret[1] = x;
        x++;
    }

    return ret;    
};

var binSearch = function(nums, start, end, target) {
    var mid = Math.floor((start + end) / 2);

    while (end >= start) {
        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }

        mid = Math.floor((start + end) / 2);
    }

    return -1;
}

其中的二分查找办法，咱们能够封装成一个办法，每次题目须要用到的时候，间接复制过去就能够了，很多常见的算法实现，纯熟应用之后都能够这么做。

后果

上面看下后果：

工夫上超过 84% 的提交，还算不错，内存应用算是中等。
一次提交通过后就能够查看其他人的提交，能够比照学习下，盲猜有人用了 js 自带的 indexOf 办法，这个办法的实现效率是比二分查找要快的。

比照

比照了下他人的提交记录，根本都应用了二分查找法，有一种不同的解法，是对二分查找稍作革新，保障每次查到的都是 target 第一次呈现的地位，而后别离找到 target、target + 1 第一次呈现的地位，因为是升序的数组，target + 1 第一次呈现的下标 – 1 就是 target 最初呈现的下标，运行速度比我下面贴的代码要快。

我思考了下，认为应该是当 target 反复次数很多的状况下，通过寻找 target + 1 来确定 target 最初的下标，效率要更快。感兴趣的同学能够深入研究下。

ARTS

题目中的 ARTS 是耗子叔在他的 左耳听风 中发动的个流动：

每周实现一个 ARTS： 至多做一个 LeetCode 的算法题、浏览并点评至多一篇英文技术文章、学习至多一个技术技巧、分享一篇有观点和思考的技术文章。（也就是 Algorithm、Review、Tip、Share 简称 ARTS）