二分查找
二分法查找单个值
题目：给定一个n个有序的（升序）数组nums和一个目标值target，写一个函数搜索nums中target，如果目标值存在返回下标，否则返回-1；
关键词：有序数组，无重复元素
难点：区间选择及循环不变量
- 在每次循环中要坚持循环不变量原则(名字不重要，怎么做很重要)
如果我们在定义数组边界的时候选取的区间为左闭右开[left, right)，那么在每一个循环中所有划分的子区间都要保证为[left, right)。同理开始定义区间为[left, right]，那么每一次的子区间都要保证为[left, right]。
以左闭右开为例，写出如下代码：
int left = 0, right = nums.size();
左闭右闭：
int left = 0, right = nums.size() - 1;
- 子区间划分及边界选取
左闭右开：区间为[left, right), 当left == right时区间是没有意义的，如[1, 1)。这个区间内不包含任何一个整数。所以循环条件为while(left < right) 不包含left等于right的情况。
当nums[mid] < target时，target值在右区间，此时需要更新左边界，假如将区间更新为[mid, right)的话，很明显mid我们是刚刚检查过的nums[mid] < target，所以更新后的区间不应该包含mid，故区间跟新为[mid+1, right);
当nums[mid] > target时，此时要要更新右边界, 假如将边界更新为[left, mid)，nums[mid]检查过了，所以区间不应该包含mid，而[left, mid)区间恰好不包含mid，更新正确
由此，不难写出如下代码：
class Solution {
public:
int search(vector<int>& nums, int target) {
// 定义区间
int left = 0, right = nums.size();
// 根据所选区间确定循环条件
while(left < right) {
int mid = ((right - left) >> 1) + left;
if(nums[mid] == target) return mid;
// 遵守循环不变量原则更新子区间
if(nums[mid] < target) {
// 更新左边界
left = mid + 1;
} else {
// 更新右边界
right = mid;
}
}
return -1;
}
};
左闭右闭：由于区间为[left, right]， 当left == right时是有意义的，如[1, 1]。区间包含正整数1。所以循环条件为while(left <= right)。
当nums[mid] < target时，区间为[left, right]，由于检查过nums[mid]，所以区间更新为[mid+1, right]; 当nums[mid] > target时，更新右边界为[left, mid-1]
代码如下：
class Solution {
public:
// 定义区间
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
// 根据区间确定循环条件
while(left <= right) {
int mid = ((right - left) >> 1) + left;
if(nums[mid] == target) return mid;
// 根据循环不变量原则更新子区间
if(nums[mid] < target) {
// 更新左边界
left = mid + 1;
} else {
// 更新右边界
right = mid - 1;
}
}
return -1;
}
};
二分法查找区间
题目：给定一个非递减的有序整数数组，和一个target，
请找出给定目标值在数组中的开始位置和结束位置，如果不存在目标值，返回[-1, -1]
经过上一道题，我们已经学会了怎么查找到target值所在的位置了，但是如果数组中有多个值都等于target，那找到的究竟是哪一个呢，当然可以通过返回当前值的坐标，分别向左向右遍历，来找到左边界和右边界，但试想如下场景，num = [ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ]，target = 5，经过第一次二分找到了最中间的5，但是不论向左遍历还是向右遍历都要n/2次，此时算法的时间复杂度退化为o(n)。
那么该怎么做呢，首先要明确的是此时我们找到了某一个target，那么假如我们要找最左边的target，我们是否可以再此用二分法查找呢，答案是肯定的，只需修改右边界，继续查找左区间是否有满足的值，循环多次直到找到最左边的target，以左闭右开区间为例，不难写出如下代码：
int searchLeft(vector<int>& nums, int target) {
// 定义区间
int left = 0, right = nums.size();
int res = -1;
// 根据所选区间确定循环条件
while(left < right) {
int mid = ((right - left) >> 1) + left;
// 遵守循环不变量原则更新子区间
if(nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] == target) {
right = mid;
} else {
// 保存当前满足要求的值的下标, 因为收缩边界后有可能没有满足要求的值了，所以要提前保存
res = mid;
// 收缩右边界查找左区间是否有满足要求的值
right = mid;
}
}
return res;
}
同理查找右边界的代码为：
int searchRight(vector<int>& nums, int target) {
// 定义区间
int left = 0, right = nums.size();
int res = -1;
// 根据所选区间确定循环条件
while(left < right) {
int mid = ((right - left) >> 1) + left;
// 遵守循环不变量原则更新子区间
if(nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] == target) {
right = mid;
} else {
res = mid;
// 收缩左边界查找左区间是否有满足要求的值
left = mid + 1;
}
}
return res;
}
整理之后的完整代码：思路来自leetcode喜刷刷
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
return {searchBound(nums, target, "left"), searchBound(nums, target, "right")};
}
int searchBound(vector<int>& nums, int target, const string& bound) {
int left = 0, right = nums.size();
// 将res初始化为-1，若查找过程中没有出现等于target的值，则res没有修改过返回-1
int res = -1;
while(left < right) {
int mid = ((right - left) >> 1) + left;
if(nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
} else {
res = mid;
// 找左边界，所以更新有边界，查找mid左边是否有等于target的值
if(bound == "left") right = mid;
// 找右边界，所以更新左边界，查找mid右边是否有等于target的值
if(bound == "right") left = mid + 1;
}
}
return res;
}
};