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

链接：34.在排序数组中查找元素的第一个和最后一个位置
难度：Medium
标签：数组、二分查找
简介：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

题解 1 - typescript

• 编辑时间：2020-12-01
• 执行用时：108ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：直接调用原生方法。

function searchRange(nums: number[], target: number): number[] {
  return [nums.indexOf(target), nums.lastIndexOf(target)];
}

题解 2 - typescript

• 编辑时间：2020-12-01
• 执行用时：80ms
• 内存消耗：41.4MB
• 编程语言：typescript
• 解法介绍：二分查找。

function searchRange(nums: number[], target: number): number[] {
  const len = nums.length;
  return [find(), find(false)];
  function find(order = true, l = 0, r = len): number {
    if (l >= r) return -1;
    const mid = ~~((l + r) / 2);
    const num = nums[mid];
    if (num > target) {
      return find(order, l, mid);
    } else if (num < target) {
      return find(order, mid + 1, r);
    } else {
      let i = mid;
      const index = order ? find(order, l, mid) : find(order, mid + 1, r);
      return index === -1 ? i : index;
    }
  }
}

题解 3 - typescript

• 编辑时间：2021-07-22
• 执行用时：68ms
• 内存消耗：40.6MB
• 编程语言：typescript
• 解法介绍：二分查找。

function searchRange(nums: number[], target: number): number[] {
  const ans: number[] = new Array(2).fill(-1);
  const i = bs(target);
  if (nums[i] !== target) return ans;
  else ans[0] = i;
  ans[1] = bs(target + 1) - 1;
  return ans;
  function bs(target: number) {
    let l = 0;
    let r = nums.length - 1;
    while (r - l > 3) {
      const mid = (l + r) >> 1;
      if (nums[mid] >= target) r = mid;
      else l = mid + 1;
    }
    for (let i = l; i <= r; i++) {
      if (nums[i] >= target) return i;
    }
    return nums.length;
  }
}