题目链接：

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）