在排序数组中查找元素的第一个和最后一个位置

题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

思路：

首先题目要求时间负责度为 O(log n)，所以想到了二分查找法。

二分查找法通常是查找某一个元素，题目中需要查找不止一个元素，所以当二分查找发找到目标元素的时候，还需要接着进行查找。

声明一个函数，该函数接受一个参数 isFindFirstIndex，表示本次查找是为了找第一次出现 target 的位置，还是最后一次。

（true 表示第一次，false 表示最后一次）

声明两个指针left、right ，然后取 mid = Math.floor((left + right) / 2)
while 循环查找，当 left > right 的时候，跳出循环
- 如果 nums[mid] === target 说明已经找到一个 target 的值了，然后根据本次查找的目的是找第一个出现的元素，还是最后出现的元素分两种情况
  - 如果本次查找的目的是为了查找第一次出现的 target ，那么记录当前的 mid 值，将 right 改为 mid - 1 继续在 mid 左侧进行查找。(因为nums是由小到大排列，所以此时需要看 mid 左侧还有没有 target 的值)
  - 如果本次查找的目的是为了找最后一次出现的 target，那么记录当前的 mid 值，将 left 改为 mid + 1,继续在 mid 右侧查找。（因为 nums 是由小到大排列, 需要看 mid 右侧是否有 target 值）

最后，调用两次这个函数，传不同的值即可。

代码：

const searchRange = (nums, target) => {
        if (nums.length <= 0 ) return [-1, -1];
        let firstIndex = -1,
            endIndex = -1;
 
        // 二分查找 target 值，参数 isFindFirstIndex 表示是否查找 target 第一次出现的下标
        const findIndex = (isFindFirstIndex) => {
            let left = 0,
                right = nums.length -1;
 
            while (left <= right) {
                const mid = Math.floor((left + right) / 2);
 
                if (nums[mid] === target) { // 若 nums[mid] === target ，此时不确定 mid 左右是否还存在 target 值，所以需要进一步判断。
                    if (isFindFirstIndex) { // 如果本次查找是为了查找 target 第一次出现的index,则继续在当前mid 位置的左侧寻找 target 值
                        right = mid - 1;
                        firstIndex = mid;
                    } else { // 如果本次查找是为了找 target 最后一次出现的位置，则应该在当前 mid 的右侧进行查找
                        left = mid + 1
                        endIndex = mid;
                    }
                }
                if (nums[mid] > target) {
                    right = mid - 1;
                }
                if (nums[mid] < target) {
                    left = mid + 1;
                }
            }
        }
        findIndex(true);
        findIndex(false);
        return [firstIndex, endIndex]
    }