前言
二分查找属于最恶心，细节最多，最容易写出死循环的算法。但是同是也是很简单的算法，因为有模板而且很容易学会。主要应用与数组有序或者无序(有规律)的情况下。
模板主要是朴素二分模板、查找左边界的二分模板、查找右边界的二分模板。
1.二分查找
题目链接：704. 二分查找 - 力扣（LeetCode）
思路图：
这道题，就是一道朴素的二分模板。
代码实现：
class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while(left <= right) { //int mid = (right + left) / 2; int mid = left + (right - left + 1) / 2; //防溢出 cout << "left : " << left << " - " << "right : " << right << endl; if(nums[mid] < target) left = mid + 1; else if(nums[mid] > target) right = mid - 1; else return mid; } return -1; } };时空分析
时间复杂度时O(logn)，底数是2。
空间复杂度为O(1)，几个变量即可。
2.在排序数组中查找第一个和最后一个位置
题目链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
思路图：
这道题相当于是查找左边界和右边界的结合，情况还是有点复杂，主要细节太多。需要分别分析，很容易写出死循环，建议每种情况先自己推荐一遍。上图解释了为什么需要有两个中点公式，左端点和右端点是不一样的，否则就会死循环。
代码实现：
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int n = nums.size(); if(!n) return {-1,-1}; int left = 0, right = n - 1, mid = 0; vector<int> ret; // 查找左端点 while (left < right) { // left == right 就是结果 mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } if(nums[left] != target) return {-1,-1}; ret.push_back(left); //查找右端点 left = 0,right = n - 1; while(left < right) { mid = left + (right - left + 1) / 2; if(nums[mid] > target) right = mid - 1; else left = mid; } ret.push_back(left); return ret; } };时空分析
时间复杂度是O(logn)，两个二分查找。
空间复杂度为O(1)，虽然定义了一个vector，但是只会消耗两个整型。
3.x的平方根
题目链接：69. x 的平方根 - 力扣（LeetCode）
思路图：
从1遍历到n，使用二分查找，注意循环条件和mid的取值公式，不是固定的。需具体问题具体分析。只要不会造成死循环即可。像这里，中点公式就只能使用另一个，否则就会死循环。做多了，你就会发现，其实就这点套路。循环条件只能是left > right，当left==right时，就是该值，应该退出。
代码实现：
class Solution { public: int mySqrt(int x) { if (!x) return x; int left = 1,right = x; while(left < right) { //必须+1防止死循环 int mid = left + (right - left + 1) / 2; // cout << "left : " << left << " - " << "right : " << right << endl; if((long)mid*mid > x) right = mid - 1; else left = mid; } return left; } };时空分析：
时间复杂度为O(logN)，一次二分查找。
空间复杂度为O(1)。
4.搜索插入位置
题目链接：LCR 068. 搜索插入位置 - 力扣（LeetCode）
思路图：
循环条件和中点处理，需要特判一下，别死循环。其他就没什么细节问题了。自己去推演一遍就很清楚了。
代码实现：
class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } if(nums[left] >= target) return left; else return left + 1; } };时空分析
时间复杂度为O(logN)，一次二分查找完成。
空间复杂度为O(1)，几个变量即可。
5.山脉数组的峰顶索引
题目链接：852. 山脉数组的峰顶索引 - 力扣（LeetCode）
思路图：
题目说了，一定存在山脉数组，所以，不用讨论不存在的情况。当二分查找完毕，数组应该是一个山顶的形状，山顶就是我们要找的结果，也就是left == right的时候。其次在讨论一下中点公式，基本思路就出来了。
代码实现：
class Solution { public: int peakIndexInMountainArray(vector<int>& arr) { int left = 0, right = arr.size() - 1; while(left < right) { int mid = left + (right - left) / 2; cout << "left : " << left << " - " << "right : " << right << endl; if(arr[mid] > arr[mid+1]) right = mid; else left = mid + 1; } return left; } };时空分析
时间复杂度为O(logN)，一次二分查找即可。
空间复杂度为O(1)。
