江苏龙网

  1. 主页 > 生活百科 > >

面试必考的「二分算法」系统梳理

二分算法

「二分」有关，算是非常普遍与重要的知识点 。然而有很多同学依然没能很好地掌握，总是会在各种细节上跌跟头，因此今天我们将对二分算法进行系统地梳理 。
「二分」一共有三类常见应用，分别是「整数二分」、「实数二分」以及「二分答案」，接下来将分别介绍这三类应用的具体形式 。
一、整数二分整数二分即为在整数集合上的二分，常见的用法有：在单调序列中查找「某个数是否出现过」、「某个数最早出现的位置」以及「>= 某个数中最小的数」等 。
解决这类问题的思想非常统一，即对坐标区间不断进行折半，以此在 O(log(n)) 的时间复杂度内确定答案，但其「实现方法」却非常多样，由此导致很多同学在此类问题上出错 。
因此接下来将通过一个例题来介绍「记录 ans」的二分实现方法，该方法较易理解且不易出错 。
34. 在排序数组中查找元素的第一个和最后一个位置题目描述给定一个按照升序排列的整数数组 nums，和一个目标值 target 。找出给定目标值在数组中的开始位置和结束位置，如果数组中不存在目标值 target，返回 [-1, -1] 。设计并实现时间复杂度为 O(log(n)) 的算法解决此问题 。
示例 1输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]示例 2输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1]示例 3输入：nums = [], target = 0输出：[-1,-1]提示

  • 0 <= nums.length <= 1e5
  • -1e9 <= nums[i] <= 1e9
  • nums 是一个非递减数组
  • -1e9 <= target <= 1e9
 题目讲解我们以数组 nums = [3 4 4 4 6], target = 4 进行举例，首先是确定 4 的开始位置，具体代码如下：
int l = 0, r = 4, ans = 0;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] >= target) {ans = mid;r = mid - 1;}else l = mid + 1;}if (nums[ans] != target) ans = -1;上述代码在二分过程中，[l, r] 始终代表二分搜索的区间，而 ans 则代表「数组中第一个 >= target」的位置 。最后再通过判断 nums[ans] 是否等于 target 来确定 target 是否存在于数组中 。
我们来模拟一下这个过程，首先二分搜索区间为 [0, 4]，因此 mid = 2 。此时 nums[2] >= 4，即 2 可能是「数组中第一个 >= target」的位置，因此更新 ans 为 2 。
面试必考的「二分算法」系统梳理

文章插图
 
又因为 nums[mid] >= 4，即答案一定不在右半区间，即 [3, 4]，于是令 r = mid - 1，搜索区间变为 [0, 1] 。此时 mid = 0，nums[0] < target，因此 mid 无法更新 ans 。
面试必考的「二分算法」系统梳理

文章插图
 
由于 nums[mid] < target，因此答案一定不在左半区间，于是 l = mid + 1，搜索区间变为 [1, 1] 。此时 mid = 1，nums[1] >= target，更新 ans = 1 。
面试必考的「二分算法」系统梳理

文章插图
 
由于 nums[mid] >= target，于是 r = mid - 1，不再满足 l <= r 的条件，二分过程结束 。最终 ans = 1，二分成功 。
通过上述这个过程，我们可以总结出「整数二分」的实现规律，首先由 while (l <= r) 来控制二分进程，每次计算 mid = (l + r) / 2，并判断 mid 是否为可能的答案 。如果是，则更新 ans，否则不更新 。另外根据 mid 判断接下来是搜索左半区间 [l, mid - 1]，还是右半区间 [mid + 1, r]，不断循环 。退出循环后，ans 即为要求的答案 。
根据上述示例，大家可以自行完成「查找 target 结束位置」的代码，并查看下述完整代码进行验证 。
class Solution {public:vector<int> searchRange(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1, ans1 = 0, ans2 = 0;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] >= target) {ans1 = mid;r = mid - 1;}else l = mid + 1;}l = 0, r = nums.size() - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] <= target) {ans2 = mid;l = mid + 1;}else r = mid - 1;}if (nums.size() && nums[ans1] == target) return {ans1, ans2};else return {-1, -1};}};二、实数二分实数二分即为实数域上的二分，即二分搜索区间 [l, r] 从整数变为了实数 。对比整数二分，实数二分的算法思想没有变化，唯一变化的只有二分实现方法 。
通常来说实数二分有两种实现方法，第一种是通过确定好的精度 eps（如 1e-6、1e-8 等），以 l + eps < r 为循环条件，每次根据在 mid 上的判定，选择左半区间 [l, mid] 或右半区间 [mid, r] 。循环结束后，l 即为最终答案，代码示例如下：
while (l + 1e-6 < r) {double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}


推荐阅读


上一篇：运动会加油稿50字有哪些？

下一篇：Bash 脚本实现每次登录到 Shell 时可以查看 Linux 系统信息