二分查找（一）

算法原理

原理：当一个序列有“二段性”的时候，就可以使用二分查找算法。

适用范围：根据规律找一个点，能将这个数组分成两部分，根据规律能有选择性的舍去一部分，进而在另一个部分继续查找。

除了最普通的二分查找，剩余的二分查找都是以 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;}
};