题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组 中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

正常二分搜索思路

在有序数组中查找元素，很容易想到二分查找。但是此题比普通二分查找多了一步，就是数组内是存在重复的元素，必须找到目标元素第一次和最后一次出现的位置。所以可以看成寻找左右边界的二分搜索。
首先要了解普通版本的二分搜索是什么思路：

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while(left<=right) {
        int mid = (left + (right - left)) / 2;
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

寻找边界的二分查找

当我们使用普通二分搜索找到目标元素时，再向左或向右线性搜索可以吗？可以，但是不好，因为这样难以保证二分查找对数级的复杂度了。

如何搜索左侧边界？

当 nums[mid] == target时， 不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

if (nums[mid] === target) {
    right = mid - 1
}

完整代码：

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right -left) / 2
        if (nums[mid] === target) {
            right = mid - 1
        } else if (muns[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        }    
    }

    // 注意点1
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

注意点1：由于 while 的退出条件是 left == right + 1，所以当 target 比 nums 中所有元素都大时，会存在以下情况使得索引越界，所以做一些兼容处理。

寻找右侧边界

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right -left) / 2
        if (nums[mid] === target) {
            left = mid + 1
        } else if (muns[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        }    
    }

    // 这里改为检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

回到原来的题目，这道题要我们同时找出左侧和右侧边界, 我先找出了左边界，然后向后while查找到右边界。这样的话算法时间复杂度应该是O(log n) + O(n)。如何同时查找左右边界来降低复杂度？未完待续。。。

var searchRange = function(nums, target) {
    let left = 0
    let right = nums.length

    while(left < right) {
        let mid = Math.floor(left + (right-left) /2)
        if (nums[mid] === target) {
            right = mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid
        }
    }
    if (left === nums.length) return [-1, -1]
    if (nums[left] !== target) return [-1, -1]


    let end = left
    while(nums[end] === nums[left]) {
        end = end+1
    }
    return [left, end-1]
};