乐趣区

关于leetcode:前端工程师leetcode算法面试必备二分搜索算法中

一、前言

  二分搜索算法自身并不是特地简单,外围点次要集中在:

  • 有序数组:指的是一个递增或者递加的区间(非凡状况如:【852. 山脉数组的峰顶索引】)
  • 两头数:用来确定搜寻指标落在左半区间还是右半区间

进入 Medium 难度之后,这两个条件个别不会间接给出,须要解题者依据题目自行结构。

二、LeetCode 实战

1、378. 有序矩阵中第 K 小的元素

  由程度和垂直方向为递增数组的条件,能够失去以后二维空间中的左上角为最小值,右下角为最大值,所以 有序数组即为最小值到最大值的整数递增序列

  题目要求计算出第 k 小的元素,那么从有序数组中筛选进去的两头数并不能间接与 k 进行比拟,须要在二维空间中找出以后两头数是第几小的数字,再与 k 进行比拟:

  • 如果以后两头数比第 k 小的元素要大,那么第 k 小元素必然在左半区间;
  • 否则必然落在右半区间;

通过以后二维数组程度和垂直方向枯燥递增的个性,能够从 左下角开始搜寻 以后两头数为第几小的数字。

相似解题思路的还有:

  • 【74. 搜寻二维矩阵】
2、875. 爱吃香蕉的珂珂

  这道题要求咱们找出一个最慢吃香蕉的速度,使得在 H 小时能够吃完 N 堆香蕉。

  珂珂最慢吃香蕉的速度是每个小时吃 1 根,最快的速度是每小时吃掉 max(N),有序数组即为 1 到 max(N) 的整数递增序列

  从有序数组中找出一个速度之后,还须要 计算以后速度下吃完所有香蕉所需的工夫和 H 相比拟

  • 如果以后速度下吃完所有香蕉的工夫大于 H,那么所须要搜寻的速度 K 必然落在右半区间;
  • 反之,K 落在左半区间;
3、658. 找到 K 个最靠近的元素

  这道题要求咱们找到一个起始下标 index,使得 [index, index + k) 中的数字最靠近 x。

  该题并没有暗藏有序数组这一条件,所以这道题目的难点在于如何通过两头下标来判断 index 落在哪个区间:

  • 首先思考数组边界的问题,如果 mid + k > arr.length – 1,那么 index 必然在落在左半区间;
  • 接下来利用最靠近 x 和优先选择最小元素(也就是优先选择右边的元素)这两个条件:如果间隔 x 右边的差值小于间隔 x 左边的差值,那么 index 必然落在左半区间;

相似解题思路的题目还有:

  • 【275. H 指数 II】
4、34. 在排序数组中查找元素的第一个和最初一个地位

  这道题目绝对比较简单,然而它与后面题目的差别在于:搜寻指标不肯定存在有序数组中,那么在搜寻完结后,就须要留神非凡状况的解决。

  通过两次二分搜寻找出目标值的高低界线下标,再将高低界线值与目标值进行比对,从而得出正确的开始下标和完结下标:

参考视频:传送门

写在最初

  算法作为计算机的基础学科,用 JavaScript 刷,一点也不丢人 ε =ε=ε=┏(゜ロ゜;)┛。

  本系列文章会别离给出一种算法的 3 种难度的总结篇(简略难度,中等难度以及艰难难度)。在简略难度中,会介绍该算法的基本知识与实现,另外两个难度,着重解说解题的思路。

  如果本文对您有所帮忙,能够点赞或者关注来激励博主。

退出移动版