简述
二分法是一种源自数学思想的朴素算法。
属于是最简单的中级算法,因为很多非计算机专业的人,也都会或多或少了解和接触二分法,因此二分法也常被一些企业用来作为综合素质的题来测试应聘者的智商和数字敏感度。
二分法的算法题目通常具有明显的暗示,当题目中明显出现了有序数组,或者O(logN)的时间复杂度要求时,一定会优先思考二分法进行搜索。
同时题目还会强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件
二分搜索的数学逻辑
- 基于左右两个端点的索引,可以在O(1)的时间里求出中点的值。
- 在数组有序的前提下,比较中点可以直接排除一半的可能。
- 因此将O(N)的搜索,简化成了O(log2N)的排除。
循环不变量思想 - 开闭区间 ⭐️
二分查找涉及的最多的就是各种边界条件.虽然逻辑比较简单,但就是写不好。例如到底是 while (left < right) 还是 while (left < = right),到底是right = middle呢,还是要right = middle - 1呢?
归根结底,问题还是出在对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
写二分法,一般有两种区间,左闭右闭即[left, right],或者左闭右开即[left, right)。我个人的习惯是用[left, right]。可以参考如下模板:
left, right = 0, len(nums) -1 while ( left <= right ): # 右边闭区间时,left <= right属于有效情况 mid = (left + right) >> 1 # 使用位运算防止大数溢出 if ( nums[mid] == target ) : return 结果 # 有的题可能还需要后续处理 if (nums[mid] > target): right = mid - 1 # mid已经判断过不符合要求,所以大胆-1 else: left = mid + 1 # 此处mid+1 同理 return 异常处理 # 通常是针对target不存在的情况下返回特定异常值
问题合集以及分析
二分法是数组题型中的经典算法,因此可以看到大多数二分算法的经典题和算法都是在Leetcode序号靠前的题目。
二分算法虽然比较直接,二分法的出题难度却比较灵活。纯粹的、最基础的二分搜索就可以单独出题,也是典型的简单题。随后,随着数组的条件开始变得抽象,题目的难度也会增加。
| 编号 | 名称 | 难度 | 贪心策略 |
|---|---|---|---|
| 704 | 二分查找 | 简单 | 最为基础的二分搜索。 |
| 35 | 搜索插入位置 | 简单 | 最为基础的二分搜索。 |
| 74 | 搜索二维矩阵 | 中等 |
难点: 数组升维 但是其实没区别。可以先通过行优先思想,确定target会出现在哪行,然后一波普通二分搜索带走。 |
| 34 | 在排序数组中查找元素的第一个和最后一个位置 | 中等 |
难点: 元素重复,答案大概率不唯一 这题二分搜索的过程其实还是一样的,但是nums[mid]==target区块对结果的处理不再是直接return,而是需要对[left, right]进行一次遍历(也可以用左右夹逼)来确定最终的【start, end】 |
| 33 | 搜索旋转排序数组 | 中等 |
难点: 数组不是无条件有序 搜索的过程中就需要处理一个旋转轴心点,需要分别处理数组为[l, r]和[l, p, r]的情况,中间p点代表的是最大值突然跌到最小值的点。但是突破点就是旋转后nums[0]一定大于nums[-1]的特性,可以在搜索中进行判断决定搜索方向。 |
| 153 | 搜索旋转排序数组中的最小值 | 中等 |
跟33题难点和解法一致。但是需要返回最小值,也就是33题中的旋转轴心点。 搜索的过程中,将mid元素和右边界不断比较,会有三种情况:
|
| 4 | 寻找两个正序数组中的最小值 | 困难 |
主要思路: 要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k//2-1] 和 pivot2 = nums2[k//2-1] 进行比较。 nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个 nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个 这样 pivot 本身最大也只能是第 k-1 小的元素 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数 |