Skip to content

Latest commit

 

History

History
266 lines (178 loc) · 19.3 KB

二分查找.md

File metadata and controls

266 lines (178 loc) · 19.3 KB

二分查找

引言

  1. 基本概念：二分查找就是从一个排好序的序列中查找一个元素，和顺序查找不同的是，二分查找通过逐步缩小搜索区间的方式将搜索范围逐渐缩小，最终定位到我们的目标值或者目标位置，在STL中，lower_bound() 和 upper_bound() 就是利用二分的思想，前者在有序数组中找到第一个大于等于的目标值的位置，后者找到第一个大于目标值的位置
  2. 排版说明：
    • 首先是套用模板法，这个很简单，就是记住一个二分查找的模板，然后根据题意套用即可，可以解决99%的问题，但对于个别特殊的问题无法解决，主要参考的是 代码随想录 和 图解二分
    • 其次是直接分析法，这个方法需要忘记所有的模板，没有所谓的「左闭右开」「左闭右闭」的概念，重点是认真理解题意，根据题目的条件分析如何缩减区间，主要参考的是 liweiwei

套用模板法1

首先说明两个概念：

  1. 左闭右闭：搜索区间范围是 [left, right]，此时循环条件是left <= right，因为left == right时区间也是存在的

    参考代码：

    int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = n-1; // 定义target在左闭右闭的区间里，[left, right]
    while (left <= right) {
        int middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            right = middle - 1; // target 在左区间，在[left, middle-1]中
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，在[middle+1, right]中
        } else {
            return middle; // 数组中找到目标值的情况，直接返回下标
        }
    }
    // 这里需要根据题意分析！！
    return right+1;
}

  2. 左闭右开：搜索区间范围是 [left, right)，此时循环条件是left < right，因为left == right时区间不存在

    参考代码：

    int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = n; // 定义target在左闭右开的区间里，[left, right) 
    while (left < right) {
        int middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            right = middle; // target 在左区间，在[left, middle)中
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，在 [middle+1, right)中
        } else {
            return middle; // 数组中找到目标值的情况，直接返回下标
        }
    }
    // 循环结束时有 left>=right，大多数情况下 left == right，但是为了不越界往往返回right
    return right;
}

套用模板法2

统一将判断条件定位 while(left < right)，根据划分区间的不同选择不同的模板

  1. 模板一

    将区间[left, right]划分为分成 [left, mid] 和 [mid + 1, right]，此时计算 mid 不需要 +1

    int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r)/2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

  2. 模板二

    将区间 [left, right]划分为分成 [left, mid-1] 和 [mid, right]，此时计算 mid 需要 +1

    int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = ( l + r + 1 ) /2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

说明：在大多数情况下，这里使用模板一可以求出左边界，使用模板二可以求出右边界，为什么是大多数情况呢？因为有的题目很特殊需要特别注意判断条件

vector<int> searchRange(vector<int>& nums, int target) {
    if(nums.empty()) return {-1,-1};
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r ) / 2;
        // 找左边界 找到第一个i nums[i] >= target 
        if(nums[mid] < target) l = mid + 1;	// 反向思考
        else r = mid;
    }
    if (nums[r] != target) return {-1,-1};  // 查找失败
    int L = r;
    
    l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r + 1)/2;
        // 找右边界 找到最后一个i nums[i] <= target
        if(nums[mid] > target ) r = mid - 1; // 反向思考
        else l = mid;
    }
    return {L,r};
}

直接分析法（推荐）

这里需要忘记前面提到的左闭右闭和左闭右开区间，根据题意分析 right 的初始值，然后分析下一轮的搜索区间是左侧还是右侧

这里根据经验，往往设置的是 while(left < right)，因为只有这样退出循环时才有 left >= right，往往会有 left == right成立， 为了不越界就使用 right 作为目标位置

常见问题

  1. 二分查找不一定要求数组有序

力扣上如「山脉数组」「选择有序数组」等可以根据 nums[mid] 的值推测两侧元素的性质，进而缩小搜索区间，这类数组都是接近有序的数组

还有如「寻找重复数」不在输入数组上做二分，而是在输入数组的最小值 min 和最大值 max 组成的连续整数数组上查找一个数，也就是搜索区间是 [min...max]

  1. 二分查找取 mid 时何时+1

首先何时+1何时不+1是为了避免死循坏，对于有偶数个元素的区间来说，使用 mid = (left+right)/2 只能取到左边的中位数，如果想要取到右边的中位数就必须+1

再来看为什么有时需要取到右边的中位数，考虑只有两个元素的区间（比如 [1,2] mid=1），利用 mid 将区间分为 [left, mid-1] 和 [mid, right]时，如果不+1则无法缩减区间，进而进入死循环

总结

  • 写成 while(left < right)，退出循环的时候有 left == right 成立，好处是：不用判断应该返回 left 还是 right；

  • 区间 [left...right] 划分只有以下两种情况：

    • 分成 [left...mid] 和 [mid + 1...right]，分别对应 right = mid 和 left = mid + 1；
    • 分成 [left...mid - 1] 和 [mid...right]，分别对应 right = mid - 1 和 left = mid，这种情况下。需要使用 int mid = (left + right + 1) / 2，否则会出现死循环，这一点不用记，出现死循环的时候，把 left 和 right 的值打印出来看一下就很清楚了；

  • 退出循环 left == right，如果可以确定区间 [left...right] 一定有解，直接返回 left 就可以，否则还需要对 left 这个位置单独做一次判断；

  • 始终保持不变的是：在区间 [left...right] 里查找目标元素。

常见题型

1. 二分求下标

在给定数组中查找符合条件的元素下标

题目 说明 题解
704.二分查找 简单的二分即可，常规思路
35.搜索插入位置 找到插入位置的索引，可以是len，因此可以设置right=len 解
300.最长上分子序列 这题DP思路比较简单，二分查找比较难 解
34.排序数组查找第一个和最后一个位置 可以总结为两个模板：查找左边界和查找右边界 解
611.有效三角形的个数 二分有两种思路：左边界和右边界，双指针：固定最长边逆序 解1 解2
659.找到K个最接近的元素 二分找到左边界，双指针 解
436.寻找右区间 使用哈希表记录第一个元素位置之后在[:][0]二分查找[:][1] 解
1237.找出给定方程的正整数解 二分利用一个变量递增，双指针利用两个变量都递增 解
4.寻找两个正序数组的中位数 直接归并比较简单，通过二分找到__分割线__比较难 解
6355. 统计公平数对的数目 排序之后二分，lower_bound，upper_bound 通过

「选择数组」和「山脉数组」：局部单调性

题目 说明 题解
33.搜索旋转排序数组 直接在循环里面定位比较直接，在外面定位思考很细节 解
81.搜索旋转排序树组II 在 33 基础上通过++left去重，或者直接while去重 解
153.旋转排列数组最小值 通过比较 mid 和 right 判断最小值在左还是右 解
154.旋转排序数组最小值II 在 153 基础上通过 -- right 去重 解
852.山脉数组的峰顶索引 找到最小满足 nums[i] > nums[i+1] 的下标 解
1095.山脉数组找目标值 三个二分：找到峰顶下标，升序找target，降序找target 解
1802. 有界数组中指定下标处的最大值 “山峰数列”求和 sum，找到满足 sum <= maxSum 的最大峰 解

2. 二分找答案

在给定的序列中找一个满足条件的答案，通过二分查找逐渐缩小范围，最后逼近到一个数

题目 说明 题解
69.x的平方根 使用除法可以避免溢出，另有一个 牛顿迭代法 解
287.寻找重复数 二分思路有点绕，循环链表思路比较直接 解
374.猜数字大小 比较简单的二分，注意一下题意就好
275.H指数 II 注意向左找还是向右找的条件 解
1283.使结果不超过阈值的最小除数 注意不整除才+1 解
1292. 元素和小于等于阈值的正方形的最大边长 二维前缀和，遍历二分 解
剑指 Offer 53 - II. 0～n-1中缺失的数字 左子数组 nums[i]=i，右子数组 nums[i]!=i 通过
1760. 袋子里最少数目的球 在[1, max(nums)]中二分找到开销（最大值）的最小值 官解
2576. 求出最多标记下标 问题的单调性，二分过程贪心检查 0x3F

3. 最大化最小值

题目 说明 题解
1552. 两球之间的磁力 猜答案 ans 越小，可以放的位置越多，越有可能 >= m，满足题意 边界
2517. 礼盒的最大甜蜜度 猜答案 ans 越小，可以选择的数越多，越有可能 >= k，满足题意 0x3F

4. 最小化最大值

题目 说明 题解
2560. 打家劫舍 IV 问题的单调性，二分找答案过程中 DP 进行判断 0x3F

总结

  1. 其实二分的题目刷多了就有经验了，最主要的分析出二分判断的条件，根据题意判断出是在左区间还是右区间查找元素。
  2. 另外对于二分意图不明显的题目需要尝试分析出题目的隐藏题意，最大值最小或者最小值最大基本上可以看做是二分的代名词。
  3. 注意问题的单调性：二分的值越大，越能/不能满足要求；二分的值越小，越不能/能满足要求，这就是单调性，就可以二分答案。

参考

  1. 大部分参考自：写对二分查找不是套模板并往里面填空，需要仔细分析题意
  2. 另模板1参考自：代码随想录
  3. 另模板2参考自：图解二分