算法：二分查找

1.二分查找

704. 二分查找 - 力扣（LeetCode）

 二分查找算法要确定“二段性”，时间复杂度为O(lonN)。为了防止数据溢出，所以求mid时要用防溢出的方式。

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;int mid = left + (right - left) / 2;//防溢出if(target > nums[mid]){left = mid + 1;}else if(target < nums[mid]){right = mid - 1;}else{return mid;}}return -1;}
};

朴素二分模版

while(left <= right){int mid = left + (right - left) / 2;//防溢出if(......){left = mid + 1;}else if(......){right = mid - 1;}else{return ......;}}

2.在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

用二分查找解决，要查找一个区间要找去左端点和右端点。

1. 查找区间的左端点

细节处理：

        1. 循环条件 left < right 而不是left <= right ，因为left == right 的时候就是最终结果，无需判断。如果判断了就会死循环（当left和right构成的区间中存在结果，并且 nums[mid] >= t时，此时mid也等于left和right，进行上述操作的时候会导致right = mid一直在原地，所以导致死循环）。

        2. 求中点的操作

left + （right - left）/ 2 要向下取整，当剩两个点让mid的指针指向left。

2.查找区间右端点

与查找区间左端点的方法类似，只是处理条件不同。

1.当nums[mid] <= target 时left == mid。

2.当nums[mid] > target 时right == mid - 1。

循环条件：left < right 和上述原因一致。

求中点的方式 left + (right - left + 1) / 2 要向上取整，当剩两个点让mid的指针指向right。

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;int begin = 0;while(left < right)//确定区间的左端点{int mid = left + (right - left) / 2;//防溢出写法if(nums[mid] < target)left = mid + 1;elseright = mid;}//判断是否有结果if(nums[left] != target)return {-1,-1};elsebegin = left;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;}//如果存在左端点，那么右端点也一定存在，所以不用判断了，直接返回return {begin, right};}
};

总结二分模版

        while(left < right){int mid = left + (right - left) / 2;if(......)left = mid + 1;elseright = mid;}while(left < right)//确定区间的右端点{int mid = left + (right - left + 1) / 2;if(......)left = mid;else right = mid - 1;}

3. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

 思路：二分查找，用左端点的模版，直接找到查找加返回要插入位置的值。如果未找到target，则检查target是否大于nums[right]：如果是，插入位置为right + 1；否则，插入位置为right（即第一个大于等于target的位置）。

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;elseright = mid;}if(target > nums[right])return right + 1;elsereturn right;}
};

4. x的平方根

69. x 的平方根 - 力扣（LeetCode）

直接将1 ~ x作为查找区间，找小于等于mid*mid的x的值

class Solution {
public:int mySqrt(int x) {if(x < 1) return 0;long long left = 0, right = x;while(left < right){long long mid = left + (right - left + 1) / 2;if(mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};

5. 山脉数组的峰顶索引

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

 运用二分查找算法，因为在山脉数组中，在前一段山脉arr[mid] > arr[mid - 1]，在后一段山脉arr[mid] < arr[mid - 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;elseright = mid - 1;}return left;}
};

6. 寻找峰值

162. 寻找峰值 - 力扣（LeetCode）

运用二分查找算法：对于区间中nums[i] 和 nums[i + 1]，如果nums[i] < nums[i + 1]，那么这段区间程上升趋势，因为nums[-1]和nums[n] = ,所以在后一段区间内一定有峰值，让left = mid + 1.

如果nums[i] > nums[i + 1]，程下降趋势，在前一段区间内一定有峰值，让right = mid。

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

7.寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

 思路：使用二分查找，因为这个数组是有二段性的（要找的值为第二段的第一个元素），将这个数组分为两段第一段的值一定比第二段的值大，所以根据nums[mid]和nums[n - 1]的关系作为比较。nums[mid]>nums[n - 1]，说明在mid第一段，所以要让left = mid + 1；nums[mid] <= nums[n - 1]时，说明mid在第二段上，要让right = mid。

第二种方法是一nums[0]作为比较值，只是这种有特殊情况，全是升序的时候会导致mid一直向后走，所以找特殊判断一下升序的情况。

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

8.点名

LCR 173. 点名 - 力扣（LeetCode）

 1.哈希表；2.直接遍历找结构；3.位运算；4.求和公式。这些方法的时间复杂度都是O(N)。

方法5：二分查找：这个数组有二段性，分成两段判断对应的值是否相等，还需要处理一下全升序的情况

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