算法原理
原理：当一个序列有“二段性”的时候，就可以使用二分查找算法。
适用范围：根据规律找一个点，能将这个数组分成两部分，根据规律能有选择性的舍去一部分，进而在另一个部分继续查找。
除了最普通的二分查找，剩余的二分查找都是以 left == right 为结束条件。
找中点 mid方法：left+(right - left)/2（查找区间左端点的情况）；left+(right-left+1)/2（查找区间右端点的情况）
循环判断结束方法：left<=right（普通二分查找） left<right（查找左边界或有边界的二分情况）
下图是找左边界的思路：将区间分为小于目标值和大于等于目标值两部分
同理，当找右区间的时候：
如何区分这些模板呢？
先将所求区间分为两个子区间，目标下标一定要为这两个子区间的区间边界处，当求左区间的端点的时候，求中点的操作是 mid = left + (right - left)/2 ，这种求中点的方式，当区间总元素数为偶数的时候，恰好求的是靠左边的那一个中间的数，而 mid = left + (right - left +1)/2 则求出的是靠右边的那一个中间的数。
将区分这两个区间的条件，作为每次二分舍去一部分的依仗，舍去不存在目标值的那部分（... = mid + 1 或 ... = mid - 1）；靠近目标值（... = mid）
二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
此题为一道普通二分题目，很简单
class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while(left<=right) { int mid = (left + right)/2; if(nums[mid]==target) return mid; else if(nums[mid]<target) left = mid + 1; else right = mid - 1; } return -1; } };
在排序数组中查找元素的第一个和最后一个位置
此题是查找左端点与查找右端点结合的题目，只需再处理一下特殊情况即可。
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if(nums.size()==0) return {-1,-1}; // 1. 找左端点 int left = 0, right = nums.size() - 1, mid = 0; vector<int> v1; while(left < right) { mid = left + (right - left) /2; if(nums[mid] < target) left = mid + 1; if(nums[mid] >= target) right = mid; } if(nums[left]!=target) return {-1,-1}; v1.push_back(left); // 2. 找右端点 left = 0, right = nums.size() - 1; while(left < right) { mid = left + (right - left + 1) /2; if(nums[mid] <= target) left = mid; if(nums[mid] > target) right = mid -1; } v1.push_back(left); return v1; } };
x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
转化为求区间的右端点的二分问题
class Solution { public: int mySqrt(int x) { if(x == 0) return 0; long long left = 1, right = x; while(left < right) { long long mid = (left + right + 1) /2; if(mid * mid <= x) left = mid; if(mid * mid > x) right = mid -1; } return left; } };
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
转化为找区间左端点的问题。其实也可以转化为找区间右端点的问题，但需要处理的细节更多！
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 + 1; else return left; } };
