Pengjielee's blog

题目

给定一个按照升序排列的整数数组 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 <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

// 查找第一个等于给定值的元素
const binarySearchFirst = (arr, target) => {
  let low = 0,
    high = arr.length - 1;

  while (low <= high) {
    const mid = parseInt(low + (high - low) / 2);

    if (arr[mid] === target) {
      // 如果是第一个元素 或者 前一个元素不等于目标值
      if (mid === 0 || arr[mid - 1] != target) {
        return mid;
      } else {
        high = mid - 1;
      }
    } else if (arr[mid] < target) { //目标值 大于 中间值， 则更新low
      low = mid + 1;
    } else { //目标值 小于 中间值， 则更新high
      high = mid - 1;
    }
  }

  return -1;
};

// 查找最后一个等于给定值的元素
const binarySearchLast = (arr, target) => {
  let low = 0,
    high = arr.length - 1;

  while (low <= high) {
    const mid = parseInt(low + (high - low) / 2);
    if (arr[mid] === target) {
      //如果是最后一个元素 或者 下一个元素不等于目标值
      if (mid === arr.length - 1 || arr[mid + 1] != target) {
        return mid;
      } else {
        low = mid + 1;
      }
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
};

var searchRange = function (nums, target) {
  const first = binarySearchFirst(nums, target);
  const last = binarySearchLast(nums, target);
  return [first, last];
};

2、合并

const binarySearch = (arr, value, first) => {
  let low = 0,
    high = arr.length - 1;

  while (low <= high) {
    const mid = parseInt(low + (high - low) / 2);
    if (arr[mid] === value) {
      if (first) {
        if (mid === 0 || arr[mid - 1] != value) {
          return mid;
        } else {
          high = mid - 1;
        }
      } else {
        if (mid === arr.length - 1 || arr[mid + 1] != value) {
          return mid;
        } else {
          low = mid + 1;
        }
      }
    } else if (arr[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
};

var searchRange = function (nums, target) {
  const first = binarySearch(nums, target, true);
  const last = binarySearch(nums, target, false);
  return [first, last];
};