前端算法面试必刷题系列[14]

24. 在排序数组中查找元素的第一个和最后一个位置 (find-first-and-last-position-of-element-in-sorted-array)

标签

• 二分查找
• 中等

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给出一个有序数组 nums 和一个数 target，要求在数组中找到第一个和这个元素相等的元素下标，最后一个和这个元素相等的元素下标。

基本思路

看到升序，有序数组想到二分查找

请看这篇 二分查找

这一题是经典的二分搜索变种题。二分搜索有 4 大基础变种题：

1. 查找第一个值等于给定值的元素
2. 查找最后一个值等于给定值的元素
3. 查找第一个大于等于给定值的元素
4. 查找最后一个小于等于给定值的元素

我们利用前面2种变种，合并便可解决问题。

步骤

1. 查找第一个值等于给定值的元素下标
2. 查找最后一个值等于给定值的元素下标
3. 合并起来

写法实现

看着长，其实真的简单，别慌

// 二分查找第一个与 target 相等的元素，时间复杂度 O(logn)
let searchFirstEqualElement = (nums, target) => {
  let [left, right] = [0, nums.length-1]
  while (left <= right) {
    pivot = left + Math.floor((right - left) / 2)
    if (nums[pivot] > target) {
      right = pivot - 1
    } else if (nums[pivot] < target) {
      left = pivot + 1
    } else {
      // 上面全都是二分查找的基本代码，一模一样
      // 就差等于的情况，我们想找到第一个与 target 相等的元素
      if ((pivot === 0) || (nums[pivot-1] !== target)) { 
        // 当上面这两种情况发生说明我们找到了『左边界』
        // 1. index等于0，没什么好说
        // 2. 当nums[pivot-1]再左边一个元素不等于target说明已经到了左边界
        return pivot
      }
      // 要不然就右边左移，也就是把pivot往前看
      right = pivot - 1
    }
  }
  return -1
}

// 二分查找最后一个与 target 相等的元素，时间复杂度 O(logn)
let searchLastEqualElement = (nums, target) => {
  let [left, right] = [0, nums.length-1]
  while (left <= right) {
    pivot = left + Math.floor((right - left) / 2)
    if (nums[pivot] > target) {
      right = pivot - 1
    } else if (nums[pivot] < target) {
      left = pivot + 1
    } else {
      // 上面全都是二分查找的基本代码，一模一样
      // 就差等于的情况，我们想找到最后一个与 target 相等的元素
      if ((pivot === nums.length-1) || (nums[pivot+1] != target)) { 
        // 当上面这两种情况发生说明我们找到了『右边界』
        // 有上面一个方法，这个就不赘述
        return pivot
      }
      left = pivot + 1
    }
  }
  return -1
}

// 最后合并就行
var searchRange = function(nums, target) {
  return [searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)]
};

console.log(searchRange([5,7,7,8,8,10], 8))

另外，如果你在面试实在想不起来咋写二分，强行写也行，实现为主。

这样也行，注意你用的是js，善用工具，也是能力。

let searchRange = (nums, target) => {
    return [nums.indexOf(target), nums.lastIndexOf(target)]
};

今天时间不多，就来一个

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦 搜索我的微信号infinity_9368，可以聊天说地 加我暗号 "天王盖地虎" 下一句的英文，验证消息请发给我 presious tower shock the rever monster，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧