【一】'二分'算法原理剖析
二分查找通常要求数据有序。其本质是通过目标值排除一半的区间，解决传统的从头到尾遍历查找。只要目标数据与目标值满足一定的大小关系，即可使用二分法。
第一套模版：
int left = 0, right = nums.size() - 1;
int mid = 0; //找左端点
while (left < right) {
mid = (right + left) / 2;
if (nums[mid] > target) right = mid - 1;
else if (nums[mid] < target) left = mid + 1;
}
第二套模板： 推论：假设找 target 连续的区间（找左端点）
首先看左边区间：如果 mid 落在左边的区间，那么 mid 不可能命中到目标值，left = mid + 1。 8 在右边的一坨中，那么 mid 不能超过这个区间（竖划线），right = mid。 mid 的中值计算应该为：left + (right - left) / 2（计算左端点）。 循环条件应该是：left < right，如果等于，会由于判断条件导致循环。 现象：如果 mid 落在左边，就必须超过竖划线收缩；在右边应该不断收缩，但是不能超过竖划线。
int left = 0, right = nums.size() - 1;
int mid = 0; //找左端点
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] >= target) right = mid;
else if (nums[mid] < target) left = mid + 1;
}
第三套模板： 推论：假设找 target 连续的区间（找右端点）
首先看左边区间：如果 mid 落在左边的区间，那么 mid 可能命中到目标值，left = mid。 mid 落在右边的一坨，那么 mid 不能超过这个区间，right = mid - 1。 mid 的中值计算应该为：left + (right - left + 1) / 2（计算右端点）。 循环条件应该是：left < right，如果等于，会由于判断条件导致循环。 现象：如果 mid 落在左边，就不能超过竖划线收缩；在右边应该不断收缩，必须要超过竖划线。
//找右端点
left = 0, right = nums.size() - 1;
while (left < right) {
mid = left + (right - left + 1) / 2;
if (nums[mid] > target) right = mid - 1;
else if (nums[mid] <= target) left = mid;
}
【二】简单的二分查找
（1）题目链接
https://leetcode.cn/problems/binary-search
（2）算法解析
这题大家套'二分算法原理剖析'的第一套模板即可。
【三】找目标范围
（1）题目链接
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
（2）算法解析
暴力解法：遍历数组，找先目标值，再看是否有连续的目标值，记录它们的下标即可。
算法解析：（以下是找的到 target 的情况，需要判断找不到的情况）
首先找左端点： 以上图为例，具备完美的边界（二段性），左边界的 8 比左边的 0,3,5,6 都要大，如果 mid 落在边界左边，不管怎样都要找比 mid 位置大的数，所以如果小于目标值，left = mid + 1。 那么如果 mid 落在>=8（左边界的 8）的位置，right 不应该跳过且收缩，所以 right = mid。
其次是右端点： 以上图为例，具备完美的边界（二段性），同理： 如果落在最右边 8 的左边，那么 left 不能跳过这段区间，只能是 left = mid，不断收缩。 如果落在最右边 8 的右边，那么 right 最终肯定要跳过才行，所以 right = mid - 1，跳过 + 收缩。
（3）代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0) return {-1, -1};
vector<int> V;
int left = 0, right = nums.size() - 1;
int mid = 0;
//找左端点
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] >= target) right = mid;
else if (nums[mid] < target) left = mid + 1;
}
if (nums[left] == target) {
V.push_back(left);
} else {//如果找不到
V.push_back(-1);
}
//找右端点
left = 0, right = nums.size() - 1;
while (left < right) {
mid = left + (right - left + 1) / 2;
if (nums[mid] > target) right = mid - 1;
else if (nums[mid] <= target) left = mid;
}
if (nums[left] == target) {
V.push_back(left);
} else {//如果找不到
V.push_back(-1);
}
return V;
}
};
【四】搜索插入位置
（1）题目链接
https://leetcode.cn/problems/search-insert-position
（2）算法解析
对于有二段线的数组 + 目标值的，我们采用二分的方法，下面是思路，采用第几套模板：
我们观察这两组值： nums = [1,3,5,6], target = 2 nums = [1,3,5,6], target = 7
可以看到：找的都是稍大的位置，比如第一组目标位置是 1 号下标，那么如果 nums[i]<2，有没有可能？完全没有，所以如果算出的目标值比小，那么 left = mid + 1，只要确定了一边，那么另一边就出来了，right = mid，循环条件是 left < right，最后肯定是 left 和 right 相遇出循环，此时判断是不是目标值，再做返回值处理。
（3）代码
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
int mid = 0;
//找左端点
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] >= target) right = mid;
else if (nums[mid] < target) left = mid + 1;
}
if (nums[left] < target) return left + 1;
return left;
}
};
【五】寻找旋转数组中的最小值
（1）题目链接
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
（2）算法解析
对于数组中找值的这类题目，我们先看有没有二段性，很明显有：数组中最小的元素。 每旋转一次是把最后一个值拿到前面来，因此，就像一个蜿蜒的山峰：
因此可以以 nums[0] 和 nums[size-1] 来作为基准值：以 nums[0] 为例： 如果比 nums[0] 大，说明在数组第二象限，left = mid + 1（因为不可能在这段区间），反之如果<它，那么可能在第四象限，就需要缩小区间，right = mid，切记不能跳过 mid，最后处理边界情况： 如果 left 一直满足 left = mid + 1，出循环也就是 left == nums.size()，比如 0,1,2,3,4，即 left=right 的时候。
（3）代码
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= nums[0]) left = mid + 1;
else right = mid;
}
return left == nums.size() ? nums[0] : nums[left];
}
};
