【秋招刷题打卡】Day02-二分系列之-二分查找

Day02-二分系列之-二分查找

前言

给大家推荐一下咱们的 陪伴打卡小屋 知识星球啦，详细介绍 =>笔试刷题陪伴小屋-打卡赢价值丰厚奖励 <=

⏰小屋将在每日上午发放打卡题目，包括：

• 一道该算法的模版题 (主要以力扣，牛客，acwing等其他OJ网站的题目作为模版)
• 一道该算法的应用题（主要以往期互联网大厂 笔试真题 的形式出现，评测在咱们的 笔试突围OJ）

小屋day02

我们预计花三天的时间来介绍和巩固二分的题目，其中包括

• 二分查找
• 二分答案
• 二分最大化最小值/最小化最大值

其中笔试常考的为后两类，今年春招中出现了不下 10 次。

引言

举个二分的例子：

比如有一个有序单调不减的数组 a r r arr arr，以及一个目标值 X X X ，要求在 a r r arr arr 中找到第一个 ≥ X \ge X ≥X 的数。

做法：每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

通过二分搜索能够有效的帮原本 O ( n ) O(n) O(n) 遍历数组的时间复杂度降为 O log ⁡ ( n ) O \log(n) Olog(n)。

当然二分能做的事远远不止如此，一个题目，如果一个区间具有单调性质，那么一定可以二分，但是如果说这道题目没有单调性质，而是具有某种区间性质的话，我们同样可以使用二分，二分的题目，往往会出现最大值最小值, 或者单调性质。题目如果出现最大的最小值，最小的最大值的类似的字眼，一般是可以使用二分来解决。

✨ 以下提供一个，本人长期使用的一个比较好用的手写二分模版

二分模版

二分模板一共有两个，分别适用于不同情况，使用时只需修改check函数即可。
算法思路：假设目标值在闭区间 [l, r] 中， 每次将区间长度缩小一半，当 l = r 时，我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加 1。

• CPP

  int bsearch_1(int l, int r)
  {
    // l 为左端点，r 为右端点，都是闭区间
    // 使用时只需修改check函数即可
      while (l < r)
      {
          int mid = l + r >> 1;
          if (check(mid)) r = mid; // check函数代表你需要进行的判断操作
                                     // 最终的答案会满足check条件
          else l = mid + 1; // 一定是这么写 不用多想
      }
      return l; // 此时的 l 为答案 (l == r)
  }
  

• Java

  public int bsearch_1(int l, int r) {
     // l 为左端点，r 为右端点，都是闭区间
    // 使用时只需修改check函数即可
      while (l < r) {
          int mid = (l + r) >> 1;
          if (check(mid)) {
              r = mid; // check函数代表你需要进行的判断操作
                       // 最终的答案会满足check条件
          } else {
              l = mid + 1; // 一定是这么写 不用多想
          }
      }
      return l; // 此时的 l 为答案 (l == r)
  }
  

• Python

  def bsearch_1(l, r):
     # l 为左端点，r 为右端点，都是闭区间
    # 使用时只需修改check函数即可
      while l < r:
          mid = (l + r) // 2
          if check(mid):
              r = mid # check函数代表你需要进行的判断操作
                      # 最终的答案会满足check条件
          else:
              l = mid + 1 # 一定是这么写 不用多想
      return l # 此时的 l 为答案 (l == r)
  

版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

• CPP

  int bsearch_2(int l, int r)
  {
     // l 为左端点，r 为右端点，都是闭区间
    // 使用时只需修改check函数即可
      while (l < r)
      {
          int mid = l + r + 1 >> 1; // 注意这里要多加 1
          if (check(mid)) l = mid; // check函数代表你需要进行的判断操作
                                    // 最终的答案会满足check条件
          else r = mid - 1; // 一定是这么写 不用多想
      }
      return l; // 此时的 l 为答案 (l == r)
  }
  

• Java

  public int bsearch_2(int l, int r) {
     // l 为左端点，r 为右端点，都是闭区间
    // 使用时只需修改check函数即可
      while (l < r) {
          int mid = (l + r + 1) >> 1;// 注意这里要多加 1
          if (check(mid)) {
              l = mid; // check函数代表你需要进行的判断操作
                       // 最终的答案会满足check条件
          } else {
              r = mid - 1; // 一定是这么写 不用多想
          }
      }
      return l; // 此时的 l 为答案 (l == r)
  }
  

• Python

  def bsearch_2(l, r):
     # l 为左端点，r 为右端点，都是闭区间
    # 使用时只需修改check函数即可
      while l < r:
          mid = (l + r + 1) // 2 # 注意这里要多加 1
          if check(mid):
              l = mid # check函数代表你需要进行的判断操作
                      # 最终的答案会满足check条件
          else:
              r = mid - 1 # 一定是这么写 不用多想
      return l # 此时的 l 为答案 (l == r)
  

什么时候使用版本1 or 2？

清隆这边给大家总结了一下：

• 如果在 if(check()) 判断之后需要 跟新(左移) 右端点的，用 版本1
• 反之，如果是需要 跟新(右移) 左端点的，用 版本2

接来下我们看看模版如何运用

标签：二分,target,nums,int,招刷题,mid,端点,打卡,check
From： https://blog.csdn.net/Qmtdearu/article/details/139887328