算法复习笔记： 双指针_二分查找篇
目录
1.二分查找（模版&细节）
2.搜索插入位置
3.搜索二维矩阵
4.寻找峰值
5.搜索旋转排序数组
6.寻找旋转排序数组的最小值
7.在排序数组中查找元素的第一个和最后一个位置
8.寻找两个正序数组的中位数
9.x的平方根
10.山脉数组的峰顶索引
11.0~n-1中缺失的数字
1.二分查找（模版）：704. 二分查找 - 力扣（LeetCode）简单
2.搜索插入位置：35. 搜索插入位置 - 力扣（LeetCode） 简单
3.搜索二维矩阵：74. 搜索二维矩阵 - 力扣（LeetCode） 中等
4.寻找峰值：162. 寻找峰值 - 力扣（LeetCode） 中等
5.搜索旋转排序数组：33. 搜索旋转排序数组 - 力扣（LeetCode） 中等
6.寻找旋转排序数组的最小值：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode） 中等
7.在排序数组中查找元素的第一个和最后一个位置：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） 中等
8.寻找两个正序数组的中位数： 4. 寻找两个正序数组的中位数 - 力扣（LeetCode）困难
9.X的平分根：69. x 的平方根 - 力扣（LeetCode）简单
10.山脉数组的峰顶索引：852. 山脉数组的峰顶索引 - 力扣（LeetCode）简单
11.缺失的第一个整数：LCR 173. 点名 - 力扣（LeetCode）简单
1.二分查找（模版&细节）
使用二分算法的前提：数据具有二段性，可以根据某个条件把数据划分成两半。
一般是mid和target比较，如果不存在target就和相邻元素比较，都不存在，就和left和right比较。
1.1.普通二分查找模版
（1）链接：704. 二分查找 - 力扣（LeetCode）简单
（2）模版：分别是三个条件。求中间的操作可以随意，并且left=mid也可以，+1和-1操作可要可不要。
while(left <= right) {int mid = left + (right-left)/2;if(……) {left = mid+1;}else if(……){right = mid-1;}else {return ……;}
}（3）代码
class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while(left <= right) {int mid = left + (right-left)/2;if(nums[mid] < target) {left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}else {return mid;}}return -1;}
}1.2.查找区间的左端点
（1）题目：在排序数组中查找元素的第一个和最后一个位置
（2）题意：根据左端点的条件将数组划分成两个部分
（3）如何二分？需要根据mid的值来判断指针移动
左指针：left = mid +1
右指针：right = mid
（4）循环结束的条件：left < right
我们需要考虑三种情况：数组中存在答案、数组中的值都大于目标值、数组中的值都小于目标值。如果left<=right是会死循环的
数组中存在答案：
当left == right时，只需要判断left所指向的是否为答案即可。所以无需再继续循环，相等时结束即可。
数组中的值都大于目标值：会一直执行right = mid操作
数组中的值都小于目标值：会一直执行left = mid + 1操作，最后不会死循环
所以当left=right时要结束循环，在外面进行结果的判断即可。所以循环结束说明left=right或者数组为空
（5）求中点操作
发生在偶数个数据时（剩下最后两个数据）求中点的操作分为求第一个中点和求第二个中点。
求第一个中点：left + (right - left)/2 要使用这个
求第二个中点：left + (right - left + 1)/2 会死循环
（6）二分查找-查找区间的左端点模版总结
while(left < right) {int mid = left+(right-left)/2;if() left=mid+1;else right = mid;
}注意：
1.循环结束条件：left < right
2.求中点：left + (right - left)/2
3.区间划分：num[mid] < target和num[mid] >= target
4.指针移动：left = mid + 1，right = mid
1.3.查找区间的右端点
（1）题意：寻找目标值在数组中出现的最右端位置，就可以将数组划分成两个部分
（2）如何二分？
当mid落在左区间时：num[mid] <= target，此时left = mid。当目标值刚好是mid时，如果+1就会跳出结果。
当mid落在右区间时，num[mid] > target，右区间是没有结果的，所以right = mid - 1
（3）循环结束条件：left < right
当left <= right也会出现死循环
（4）求中点操作：left + (right - left + 1)/2
采取left + (right - left)/2会死循环
（5）二分查找-查找区间的左端点模版总结
while(left < right) {int mid = left+(right-left+1)/2;if() left=mid;else right = mid - 1;
}2.搜索插入位置
（1）链接：35. 搜索插入位置 - 力扣（LeetCode）简单
题意：如果找到目标值就返回目标值的下标，没找到这返回合理的插入位置，保存数组升序
（2）思路：使用查找左端点模版。
把数组分成两段，左边的值是num[x] < target，右边的值是num[x] >= target
如果存在答案，则left指针会落在答案上。
（3）代码
class Solution {public int searchInsert(int[] nums, int target) {//寻找左端点//左边区间：num[x] < t 右边区间：num[x] >= tint n = nums.length;int left = 0, right = n - 1;while(left < right) {int mid = left + (right - left)/2;if(nums[mid] < target) {left = mid + 1;}else {right = mid;}}//1.最后left落在>=t的位置上，正常直接返回left位置即可//2.如果数组中不存在比target大的，那么就返回left+1if(nums[left] < target) return left + 1;return left;}
}3.搜索二维矩阵
（1）链接：74. 搜索二维矩阵 - 力扣（LeetCode）中等
题意：每行从左到右升序，每列从上到下升序
（2）思路：从右上角开始遍历二维矩阵
（3）代码
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int n = matrix.length, m = matrix[0].length;//1.从右上角开始查找//2.如果当前值 < target : 则往下走left++//3.如果当前值 > target : 则往左边走right--int left = 0, right = m-1;while(left < n && right >= 0) {if(matrix[left][right] < target) {left++;}else if(matrix[left][right] > target) {right--;}else {return true;}}return false;}
}4.寻找峰值
（1）链接：162. 寻找峰值 - 力扣（LeetCode）中等
题意：峰值元素比它左右的元素都大。然后左边和右边都是趋于无穷小，所以肯定存在峰值
（2）思路：根据两个相邻元素划分区间，所以二段性是有答案和没有答案
如果mid < mid+1，说明右边肯定存在峰值（最右边无穷小）left = mid + 1
（3）代码
class Solution {public int findPeakElement(int[] nums) {//左边和右边是无穷很小，说明中间的区间[0,n-1]是肯定存在峰值的int n = nums.length;int left = 0, right = n - 1;while(left < right) {int mid = left + (right - left)/2;if(nums[mid] < nums[mid+1]) { //mid mid+1区间是上升趋势/，说明峰值在右边肯定存在一个（因为右边区域无穷小）left = mid + 1;}else { //mid mid+1是下降趋势，说明答案在左边存在一个（最左边区域区域无穷小）right = mid;}}return left;//mid不会越界的原因:只有一个元素时循环结束，当剩余两个元素时刚好不越界，下一步就结束循环了}
}5.搜索旋转排序数组
（1）链接：33. 搜索旋转排序数组 - 力扣（LeetCode）中等
题意：在旋转数组中找目标值，找到返回下标，没找到返回-1
（2）思路
（3）代码
class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while(left <= right) { //这里可以用=，不会死循环的原因：left和right都是mid+1或者mid-1int mid = left + (right - left)/2;//1.判断mid是否为答案if(nums[mid] == target) {return mid;}//2.判断mid落在哪一个区间AB和CD两段上升区间:CD区间的值都小于AB的if(nums[mid] >= nums[left]) { //mid落在AB区间或者[left,right]是一段上升区间//判断target值和mid的位置（mid此时肯定不是目标值）//3. nums[left] <= target < nums[mid] if(target >= nums[left]&& target < nums[mid]) right = mid - 1;//4.在AB段的(mid,B]区间和CD段区间else left = mid + 1;}else {//mid落在CD区间//5.落在CD段：nums[mid] < target <= nums[right]if(target > nums[mid] && target <= nums[right]) left = mid + 1;//6.另一半区间else right = mid - 1;}}// return nums[left]==target?left:-1;return -1;}
}6.寻找旋转排序数组的最小值
（1）链接：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）中等
（2）思路：数组划分成AB、CD两段上升，正常情况第一段肯定大于第二段，所以我们要在第二段寻找答案，也就是left=mid+1。
什么时候在第一段：[left,right]是一整段上升区间
（3）代码
class Solution {public int findMin(int[] nums) {//数组呈现两段上升趋势，第二段上升的一定比较第一段小，否则就只有一段int left = 0, right = nums.length - 1;while(left < right) {//数组分为AB、CD两段。都是严格递增的，AB段的数字都大于CD段的//如果mid落在AB段，则说明,最小值在CD段//判断条件：mid的值大于left端和right的，如果数组有序则不成立int mid = left + (right - left)/2;if(nums[mid] >= nums[left] && nums[mid] > nums[right]) { //mid落在第一段上升区间，left = mid + 1;}else {right = mid;}}return nums[left];}
}7.在排序数组中查找元素的第一个和最后一个位置
（1）链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）中等
（2）思路
只需要套入：查找左区间端点 和 查找右区间端点 模版即可
（3）代码
class Solution {public int[] searchRange(int[] nums, int target) {int n = nums.length;int left = 0, right = n - 1;int[] ret = {-1,-1};if(n==0) return ret;//1.寻找左端点while(left < right) {int mid = left + (right - left)/2;if(nums[mid] < target) { //目标值在mid右边left = mid + 1;}else {//在左边right = mid;}}if( nums[left] == target) ret[0] = left;//2.寻找右端点right = n - 1;while(left < right) {int mid = left + (right - left+1)/2;if(nums[mid] <= target) {left = mid;}else {right = mid - 1;}}if(nums[right] == target) ret[1] = right;return ret;}
}8.寻找两个正序数组的中位数
（1）链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）困难
（2）思路：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
我们的目的就是找出这两根分割线，就能找出中位数。
正确的分割线满足的条件：m = nums1.length; n = nums2.length
- 分割线左边的元素个数之和: countLeft = （n+m+1) / 2
- nums1分割线左边元素个数：假设为i，nums2分割线左边元素个数：j = countLeft - i （知道i就能求j）
- 分割线左边的值 <= 分割线右边的值
所以正常暴力解法：枚举所有的i，i=0,1,2,3 ……
暴力这里不介绍，重点介绍使用二分查找去找这个i
（3）代码
9.x的平方根
（1）链接：69. x 的平方根 - 力扣（LeetCode）简单
题意：求x的平方根，并舍去小数部分。如8的平方根是2
（2）思路：从0 ~ x遍历里面的数，如果mid^2比x大，那么这个数和它右边区间都不存在答案，如果小于等于，则存在答案
（3）代码
class Solution {public int mySqrt(int x) {//寻找右端点,mid ^ 2//左边区间：num[x] <= mid^2 ;右边区间：num[x] > mid^2//为什么？要舍去小数部分，说明平分大于x，则不存在答案long left = 0, right = x;while(left < right) {long mid = left + (right - left + 1)/2;if(mid * mid <= x) {left = mid;}else {right = mid - 1;}}return (int)left;}
}10.山脉数组的峰顶索引
（1）852. 山脉数组的峰顶索引 - 力扣（LeetCode）简单/中等
（2）思路
如下
（3）代码
class Solution {public int peakIndexInMountainArray(int[] arr) {//数组趋势，先上升再下降//如果mid < mid+1，呈上升趋势，说明答案在[mid+1,right]//mid > mid+1，呈下降趋势，说明答案在[mid,right]int left = 0, right = arr.length - 1;while(left < right) {int mid = left + (right - left)/2;if(arr[mid] < arr[mid+1]) left = mid + 1;else right = mid;}return left;}
}11.0~n-1中缺失的数字
（1）链接：LCR 173. 点名 - 力扣（LeetCode）简单
（2）思路：二段线，寻找左端点（第一次下标和值不对应的点）
（3）代码
class Solution {public int takeAttendance(int[] records) {//另一个题目：0~n-1缺失的第一个数字//二分区间：左边区间都是值和下标对应的；右边区间开始不对应（有一种特殊情况）int left = 0,right = records.length - 1;while(left < right) {int mid = left + (right - left)/2;if(records[mid] == mid) {left = mid + 1;}else {right = mid;}}if(records[left] == left) return left + 1; //如果0~n-1都出现，那就返回nreturn left;}
}