核心思想 #

通过二分算法实现查找一个元素在升序排列的数组中的起始位置和终止位置，可以按照以下步骤：

• 定义一个函数 binarySearch，接收三个参数：一个有序数组 arr，需要查找的元素 target，以及一个标志位 findFirst，告诉函数要查找的是元素的起始位置还是终止位置。如果 findFirst 为 true，则查找出现位置的起始位置，否则查找出现位置的终止位置。

• 在函数内部定义两个指针，left 和 right，分别指向数组的起始位置和终止位置。

• 进入 while 循环，循环条件为 left <= right。循环体内，定义 mid 指针，指向 left 和 right 的中间位置。

• 判断当前 mid 指针指向的元素值是否等于目标元素 target。如果是，继续操作；否则，根据数组是升序还是降序进行移动 left 或 right 指针。

• 如果查找起始位置，那么当 mid 指针指向的元素值等于目标元素时，需要继续向左查找，将 right 指针移动到 mid-1 的位置；否则，需要向右查找，将 left 指针移动到 mid+1 的位置。

• 如果查找终止位置，那么当 mid 指针指向的元素值等于目标

以下是使用二分算法实现在升序排列整数数组中查找元素起始和终止位置的 JavaScript 代码： #

function searchRange(nums, target) {
  
    const range = [-1, -1];
    const leftIndex = binarySearch(nums, target, true);
    if (leftIndex === nums.length || nums[leftIndex] !== target) {
        return range;
    }
    range[0] = leftIndex;
    range[1] = binarySearch(nums, target, false) - 1;
    return range;
    
}

function binarySearch(nums, target, findFirst) {
    // 模板语法
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target || (findFirst && nums[mid] === target)) {
            right = mid - 1;
        } else if (nums[mid] < target || (!findFirst && nums[mid] === target)) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return left;
      // 模板语法
}

代码讲解： #

searchRange ： 函数 searchRange 实现了题目要求的查询操作。它首先使用 binarySearch 函数查找元素 target 在数组中的起始位置 leftIndex，然后再使用 binarySearch 函数查找元素 target 在数组中的终止位置 rightIndex，并对结果进行判断和返回。

binarySearch ： 函数 binarySearch 实现了二分查找算法。它使用两个指针 left 和 right 分别指向数组的起始位置和终止位置。在 while 循环内，它将 mid 指针指向 left 和 right 的中间位置，并逐步缩小查找范围。同时，根据元素与 target 的大小比较，移动 left 或 right 指针。当 mid 指向的元素值等于 target 时，返回 mid 指针的位置 index。如果没有找到 target，则返回 left 指针的位置。当查找起始位置时，需要继续向左缩小查找范围，因此返回 left 所在位置。而查找终止位置时，返回 left 所在位置减 1 的位置。