【基础算法总结】二分查找

算法原理：

这道题是二分算法中最简单最朴素的一道题。
我们知道只要数组里的一个位置能使数据具有二段性就可使用二分，这个位置其实可以是中间点，也可以是⅓点，¼点…但是经过前人验证可知，找中间点是效率最高的。

算法流程如下：
(1) 定义left ，right 指针，分别指向数组的最左最右。
(2) 找到待查找区间的中间点 mid ，找到之后分三种情况讨论：
i. arr[mid] == target 说明正好找到，返回 mid 的值；
ii. arr[mid] > target 说明 [mid, right] 这段区间都是⼤于 target 的，因此舍去右边区间，在左边[left, mid -1] 的区间继续查找，即让 right = mid - 1 ，然后重复2 过程；
iii. arr[mid] < target 说明 [left, mid] 这段区间的值都是⼩于 target 的，因此舍去左边区间，在右边[mid + 1, right] 区间继续查找，即让 left = mid + 1 ，然后重复2 过程；
(3) 当 left 与 right 错开时，说明整个区间都没有这个数，返回-1 。

细节/技巧问题：

(1) 循环结束的条件。即使 [left,right] 的区间一直缩小，指向同一个数，这个数也是需要比较的，所以结束的条件是 left > right，直到两者彻底错开才结束。
(2) 求中间位置的坐标。一般求法是 mid = (left + right) / 2，但是这种方法会有数据溢出的风险，所以建议使用 mid = left + (right - left) / 2。
(3) 时间复杂度: O(logN)。其实就是看循环执行多少次：

代码实现：

class Solution 
{
public:int search(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) right = mid - 1;else if(nums[mid] < target) left = mid + 1;else return mid;}return -1;}
};

总结朴素二分模板：

算法原理：
这是一道如何用二分查找左右端点的模板例题。下面的内容将详细分析如何用二分查找左右端点的核心代码和细节问题：

1.查找区间左端点：

细节问题：

2.查找区间右端点和细节问题：

代码实现：

class Solution 
{
public:vector<int> searchRange(vector<int>& nums, int target) {// 特殊情况if(nums.size() == 0) return {-1, -1};// 找左端点int left = 0, right = nums.size() - 1;vector<int> ret;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}// 判断是否有结果if(nums[left] == target) ret.push_back(left);else return {-1, -1};// 找右端点left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}// 跳出循环后就可以不用判断了，因为只要有左端点就一定有右端点// 只是左右端点相不相等的问题ret.push_back(right);return ret;}
};

这道题其实还有一个细节/技巧问题：当左端点存在是，右端点一定是存在的，只是左右端点相不相等的问题，所以查找右端点时可以不用判断。

总结二分模板：

算法原理：

首先分析出 “二段性” ：

假设 ret 是要返回的结果，根据这个值，则 ret 的左半区间(包括ret)的每个数平方后都是小于等于 x 的，右半区间的每个数平方后都是大于 x 的，这就是本题的 “二段性”。

代码实现：

class Solution 
{
public:int mySqrt(int x) {// 处理特殊情况if(x == 0) return 0;int left = 1, right = x;while(left < right){long long mid = left + (right - left + 1) / 2;if(mid * mid <= x) left = mid;else right = mid - 1;}return left;}
};

算法原理：
首先分析出 “二段性” ：

假设返回的插入位置是 ret ，那么就有两种情况：
(1) 当目标值存在时，就返回对应值的下标
(2) 当目标值不存在时，它的插入位置恰好就是第一次出现比目标值大的那个数的位置或是数组的最后一个位置。
结合这两种情况，最终找的这个位置上的值是大于等于目标值的。
所以 ret 对应值的左半区间是小于目标值的，右半区间(包括 ret 对应值)是大于等于目标值的。这就是本题的 “二段性”。

细节问题：

当跳出循环时，说明left和right已经相等了，如果此时对应的值小于目标值，说明已经到最后的位置了，并且不存在目标值，所以返回的是下一个位置。

代码实现：

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) right = mid;else left = mid + 1;}// 错误的//return left == nums.size() - 1 ? left + 1 : left;// 走到这里，说明left和right已经相等了，如果此时对应的值小于目标值// 说明已经到最后的位置了，并且不存在目标值，返回的是下一个位置return nums[left] < target ? left + 1 : left;}
};

算法原理：

这道题的数据由峰顶的元素天然的被分成两段：如图，左半段的数据严格遵守 arr[i] > arr[i-1]，右半段的数据严格遵守 arr[i] < arr[i-1]。

二分核心流程：

代码实现：

class Solution 
{
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] > arr[mid-1]) left = mid;else if(arr[mid] < arr[mid -1]) right = mid - 1;}return left;}
};

算法原理：

我们把这道题抽象出来，分析出"二段性"：
假如我们选择 i 位置，根据 i 位置的值和 i+1 位置的值分类讨论：
(1) arr[i] > arr[i+1]，如图1，所以在左边区间中至少会存在一个峰值，因为左边是从负无穷开始的，只能是先有上升趋势才有下降趋势，但是右边区间不一定，因为有可能是一直下降的。
(2) arr[i] < arr[i+1]，如图2，与前面相反，左边区间可能没有峰值，右边区间中至少会存在一个峰值。
这就分析出了本题的"二段性"，根据 arr[i] 和 arr[i+1] 的值的关系可以分数组为两个区间，去其中一个区间里搜索结果。

二分核心流程：

代码实现：

class Solution 
{
public:int findPeakElement(vector<int>& arr) {int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(arr[mid] < arr[mid+1]) left = mid + 1;else if(arr[mid] > arr[mid+1]) right = mid;}return left;}
};

算法原理：

先分析出本题的"二段性"，可以把旋转后的数组以最大值为界线，抽象为"两条直线"，如图：可以清楚的看见具有"两段性"。可以以D点作为参照物，AB段区域的元素都大于D点值，CD段的都小于等于D点值，而要找的最小值就是C点。所以就是找右边区间的左端点。

二分核心流程：

代码实现：

class Solution 
{
public:int findMin(vector<int>& nums) {int left = 0, n = nums.size(), right = n- 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[n-1]) left = mid + 1;else right = mid;}return nums[left];}
};

算法原理：

这道题很简单，也很多解。可用的解法有：一直接遍历找结果，二使用高斯求和公式，三使用哈希思想，四使用位运算，五二分查找。其中前面四种解法的时间复杂度都是O(N)，最后一种是O(logN)。这里重点介绍二分查找。

首先分析出"二段性"：
写出下标，不难发现虚线左边的区域中的数和下标是一一对应的，虚线右边就不是，这就是"二段性"。

二分核心流程：

代码实现：

class Solution 
{
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(records[mid] == mid) left = mid + 1;else right = mid;}return left != records[left] ? left : left+1;}
};

下面是其他解法的代码，仅供参考：

(1) 直接遍历找结果

class Solution 
{
public:int takeAttendance(vector<int>& records) {int ret = 0;for(auto e : records)if(ret == e) ret++;return ret;}
};

(2) 使用高斯求和公式

class Solution 
{
public:int takeAttendance(vector<int>& records) {int sum = 0, tmp = 0, n = records.size();for(auto e : records) sum += e;tmp = (0 + n) * (n+1) * 1.0 / 2.0; // 高斯求和公式return tmp - sum;}
};

(3) 使用哈希思想(最慢)

class Solution {
public:int takeAttendance(vector<int>& records) {unordered_set<int> s;for(auto e : records) s.insert(e);for(int i = 0; i <= records.size(); i++)if(s.count(i) == 0) return i;return -1;}
};

(4) 使用位运算

class Solution {
public:int takeAttendance(vector<int>& records) {int ret = 0;for(int i = 0; i <= records.size(); i++)ret ^= i;for(auto e : records)ret ^= e;return ret;}
};