写在前面
好久没刷题了, 最近有小伙伴问我力扣的 34 题, 正好对二分查找做个总结.
理论基础
二分查找, 又称折半查找, 主要是针对连续的数组或者字符串, 用来查找某一类特定的元素, 注意这里说的是一类, 因为可能不是确定的值, 而是满足条件的值, 并且每一次查找都能过滤一半不满足指定条件的元素, 由此来提高查找效率.
这里先给出最为常用的二分查找模板, 用于在 不重复 的有序数组中找到某特定元素, 如果找不到就返回-1.
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[m] == target)
return m;
else if (nums[m] > target)
r = m - 1;
else
l = m + 1;
}
return -1;
}
};
当然, 根据这个模板, 可以变式出很多题目, 例如力扣的搜索插入位置
对这个题来说, 主要多了对于大于还是小于 target 的讨论, 换句话说, 就是在模板的基础上, 未找到 target 不是返回-1 而是 l.
有重复元素
上面讨论了无重复元素的有序数组, 此时需要研究一下对一个非递减数组, 含有重复元素的情况, 如何查找第一个出现的元素的下标呢?
本质上还是套模板, 但是要思考一下边界的判断条件, 在模板中, 找到了等于 target 的元素时直接返回下标, 但是如果有重复元素, 直接返回的话有可能是第一个出现的元素, 那么此时边界应该向左边收缩, 为什么这么说? 来看下面这个例子.
nums = [5,7,7,8,8,10] target=7
在第一轮查找中, l=0, r=5, 所以 m=2, 此时nums[m]=7, 但是 2 并不是 7 第一次出现的下标, 所以这时候还要收缩边界, 怎么收缩呢? 当然是要令 r=m-1, 也就是说把m 及其右边的元素排除出搜索区间, 这样才能保证收缩到最后返回的下标 l 是target第一次出现的下标.
继续思考一下第二轮搜索, 此时 l=0, r=1, 所以 m=0, 此时 nums[m]=5, 显然边界要向右边收缩, 即 l=m+1, 即l=r=1.
最后就是第三轮搜索, 此时l=r=m=1, 满足 nums[m]=target, 还要向第一轮查找一样收缩一次, 即 r=m-1=0, 现在就可以跳出循环了, 因为我们已经找到了满足条件的下标, 即 l=1.
综上所述, 在判断
nums[m]=target时候, 需要跟nums[m]>target的情况合并一下, 才能在有重复元素的有序数组二分查找中找到第一个出现元素的下标.
代码表示为:
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[m] < target) {
l = m + 1;
} else { // 两种情况合并了
r = m - 1;
}
}
return l;
}
};
实战: 做做 34 题
有了上面对于有重复元素数组二分查找的分析, 做 34 题其实就不难了, 需要找两段, 第一段也就是第一次出现的元素, 直接套上面的代码, 那对于最后一次出现的元素下标呢?
这时候还要用非递减这个条件, 转变一下思路, 最后一次出现的元素的下标可以用搜索 target+1 这个值来完成, 知道了 target+1的下标, 减去 1 不就是最后一次出现的元素的下标了吗?
直接写代码, 这里我用 C++11 的 lambda 封装了一下, 再加上判断-1 的代码就可以通过本题了.
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
if (!n) {
return {-1, -1};
}
auto f=[&](int ta) {
int l{}, r{n-1};
while (l <= r) {
int m=l+(r-l)/2;
if (nums[m] < ta) {
l=m+1;
} else {
r=m-1;
}
}
return l;
};
auto l = f(target);//left bound
auto r = f(target+1);
if (l<0 or r>n or l>=r) {
return {-1,-1};
}
return {l, r-1};
}
};
来一份 Java 代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return new int[]{-1, -1};
}
int[] result = new int[2];
int left = binarySearch(nums, target, true);
int right = binarySearch(nums, target, false);
if (left >= n || nums[left] != target) {
return new int[]{-1, -1};
}
result[0] = left;
result[1] = right - 1;
return result;
}
private int binarySearch(int[] nums, int target, boolean isLeft) {
int left = 0;
int right = nums.length - 1;
int result = nums.length;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target || (isLeft && nums[mid] == target)) {
right = mid - 1;
result = mid;
} else {
left = mid + 1;
}
}
return result;
}
}