学习笔记一 深入理解二分法
二分法的使用前提
二分法是进行查找最基础的方法。
由于实现方法是使用 left，right 两个指针，每次将搜索区间缩小一半，因此它是一种时间复杂度为 O(logn) 的方法。
在使用二分法时，一定要注意以下几点：
- 数组应该是分段有序的，这样有利于缩小搜索区间。
- 如果数组中存在重复元素，那么二分法返回的下标便不是唯一的，根据区间的不同定义可以返回下标的左界和右界。
- 二分法的逻辑十分简单，但边界条件的判断是重中之重，要将两种不同的区间定义辨析清楚。
- 定义 mid 时应该使用 int mid = left + (right - left) / 2 ，这样可防止(left + right) 溢出整型范围。
二分法的两种区间定义
接下来的内容我们以一道简单例题展开：力扣704.二分查找.
一、左闭右闭区间
第一种写法，我们定义 target 是在一个左闭右闭的区间里，也就是[left, right]。
- 首先定义区间初始长度时，区间左右下标应该和数组左右下标等同。
int left = 0, right = num.size() - 1;
- 在左闭右闭区间 [left, right] 中，那么 left = right 等式便是有意义的，因此在left = right时不能结束循环。
while (left <= right) //在left=right时循环继续
- 在缩小区间时，nums[mid] 已经是确定小于 target 了，也就是说 target 的下标区间不可能包含 mid，因此缩小后的闭区间左界应该是 mid + 1，即 left = mid + 1 ；同理有right = mid - 1。
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid - 1;
}
详细代码如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else return mid;
}
return -1;
}
};
二、左闭右开区间
第二种写法，我们定义 target 是在一个左闭右开的区间里，也就是[left, right)。
- 由于右边是开区间，在定义区间初始长度时，就要注意区间右界应该是数组右界 + 1。
int left = 0, right = num.size();
- 在左闭右开区间 [left, right) 中，left = right 是没有意义的，因此在left = right时应该结束循环。
while (left < right) //在left=right时循环已停止
- 在缩小区间时，左边的闭区间和上面的类似；由于 target 的下标不包括 mid，而右边的开区间边界 right 也不包括在区间里，因此缩小后闭区间右界应该是 right = mid 。
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid;
}
详细代码如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid;
}
else return mid;
}
return -1;
}
};
