相信大家对二分查找都不陌生，或者对其原理大概有个了解，但是为什么很多同学对于二分查找法一看就会，一写就废？
通过几道题目，让同学们对二分查找有更深刻的认识。接下来就是深度剖析的时刻！
题目1：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例1：
输入: nums = [-1,0,3,5,9,12], target = 5
输出: 3
解释: 5 出现在 nums 中并且下标为 3 示例2：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 解题思路：
所谓二分查找，就像打了一个结的绳子，我们通过对折越来越靠近结点。前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。
二分查找：定义查找的范围 [left,right] 。每次取查找范围的中点 middle，比较数组下标 middle 和 left、right 的大小。因此可将查找范围缩小一半。
代码：
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size() - 1;// 定义target在左闭右闭的区间里，[left, right]
while(left <= right)
{
int middle = left + (right - left) / 2;// 防止溢出 等同于(left + right)/2
if(nums[middle] > target)
{
right = middle - 1;// target 在左区间，所以[left, middle - 1]
}
else if(nums[middle] < target)
{
left = middle + 1;// target 在右区间，所以[middle + 1, right]
}
else
{
return middle;// 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
};深度剖析：
考虑什么情况下，跳出while循环？数组中包含目标值的时候，在 left = right ，下一次跳出循环 ；或者 nums[middle] = target 时，跳出循环。
我们主要探讨数组中没有目标值的时候，又是怎么样跳出循环的呢？
- left 和 right 的位置有且仅有两种情况：
- left = right = middle，此时还没有找到目标值。由于没有目标值，所以不是 right = middle -1 就是 left = middle +1 ，再次进入循环，不满足 left <= right ,跳出循环！
- left = right - 1 = middle，此时还没有找到目标值。由于没有目标值，所以不是 right = middle -1 就是 left = middle +1 ，当 left = middle +1 时，回归第一种情况； 当 right = middle -1 时（left > right），再次进入循环，不满足 left <= right ,跳出循环！
在数组中没有目标值时，如果我们知道最后一次循环以及何时跳出循环，就等于直接到二分查找的最后一步了，这对我们理解代码事半功倍！
如果没有找到目标值，那么目标值应该插入到数组的哪个位置呢？换句话说，就是返回应插入的数组下标。
解题：这时候就用到了 left 和 right 的位置有且仅有两种情况：
- 情况1：left = right = middle，若目标值在 middle 左，则 right = middle -1，跳出循环。此时应该返回 right + 1 或 left ；若目标值在 middle 右，则 left = middle +1，此时应该返回 right + 1 或 left 。
- 情况2：若目标值在 middle 左，则 right = middle -1（left > right），此时应该返回 right + 1 或 left ；若目标值在 middle 右，则 left = middle +1，即回归情况1。
代码：
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size() - 1;
while(left <= right)
{
int middle = left + (right - left) / 2;
if(nums[middle] > target)
{
right = middle - 1;
}
else if(nums[middle] < target)
{
left = middle + 1;
}
else
{
return middle;
}
}
return left; // 或者 return right + 1;
}
};题目2：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
示例1：
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]解题思路：
寻找 target 在数组里的左右边界，有如下三种情况：
- 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
- 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
- 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
总之，我们需要通过二分法去寻找左右边界！
代码1：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int first = firstPosition(nums, target);
int second = secondPosition(nums, target);
if (first == -1) {
return { -1,-1 };
}return { first,second };
}
private:
int firstPosition(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid;
}
}
if (nums[left] == target) {
return left;
}return -1;
}
int secondPosition(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
left = mid;
}
}return left;
}
};深度剖析：
情况1：此时退出循环条件就是上面的情况1，即 left = right = middle，而且数组中包含目标值。
情况2：数组[1,3]，targrt = 0；此时退出循环条件就是上面的情况2；此时 right = -1，所以代码中返回的都是 left。
代码2：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
// 情况一
if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
// 情况三
if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
// 情况二
return {-1, -1};
}
private:
int getRightBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else { // 寻找右边界，nums[middle] == target的时候更新left
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
int getLeftBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
};深度剖析：
在包含目标值情况下，此代码不管寻找左边界还是右边界，最终都会变为情况1：即 left = right = middle，正是 target 的位置。
最后，在理解二分查找原理以及何时退出循环后，选择STL解题也未尝不可！
参考：代码随想录、力扣