我要成为算法高手-二分查找篇

当数组具有二段性时，可以使用二分查找，二分查找是什么？二段性又是什么？请看题目1

题目1：二分查找

题目链接：704. 二分查找 - 力扣（LeetCode）

暴力解法：

从左往右依次遍历，如果找到返回结果，如果没找到返回-1

二分查找解法：利用数组有序的特点，对暴力解法进行优化，在数组中选取某个位置的值与目标值对比，对比之后能够划分出两个区间，一个区间是小于目标值的，另一个区间是大于目标值的，因此我们可以一口气筛选掉一部分的数据。那么选取哪个位置比较合适？根据概率学的理论，选取数组二分之一位置比较合适，时间复杂度最好

核心思路：

细节问题：循环何时结束？

当 left>right时，循环结束，left和right区间的数是没有判断的，所以当left和right同时指向一个数时(left=right)，循环仍然进行。

二段性：根据规律在数组中选取某个位置之后能够把数组划分出两个区间，根据规律我们可以舍去掉一个区间，进而能在剩下的区间寻找结果。

代码实现：

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length-1, ret = -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 {ret = mid;break;}}        return ret;}
}

总结朴素二分模版

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

根据题目要求,根据二段性来填写(…)

还有一个版本

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

上面两个区别是：如果数组元素个数是偶数，+1和不+1，mid位置不一样，但是对于朴素版本的模版来说，加不加1都无所谓

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

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

暴力解法：

非常简单粗暴：

class Solution {public int[] searchRange(int[] nums, int target) {int[] ret = new int[]{-1,-1};if(nums==null){return ret;}for(int i=0;i<nums.length;i++) {if(nums[i]==target) {ret[0]=i;break;}}for(int i=nums.length-1;i>=0;i--) {if(nums[i]==target) {ret[1]=i;break;}}return ret;}
}

二分查找思路如图

代码实现：

class Solution {public int[] searchRange(int[] nums, int target) {int[] ret = new int[2];ret[0] = -1;ret[1] = -1;if(nums.length==0){return ret;}//求左端点int left = 0,right=nums.length-1;while(left<right){int mid = left+(right-left)/2;if(nums[mid]<target){left = mid+1;} else {right = mid;}}//此时,left=right//判断if(nums[left]==target){ret[0] = left;} else {//没找到return ret;}//求右端点left = 0;right = nums.length -1;while(left<right){int mid = left+(right-left+1)/2;if(nums[mid]>target){right = mid-1;} else{left = mid;}}//此时,left=rightif(nums[right]==target){ret[1] = right;} else {return ret;}return ret;}
}

总结二分模版

1、

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

2、

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

根据题目的要求，判断left和right，接着来确定求mid时是否需要+1

题目3：x的平方根

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

解题思路如图：

根据最终返回的结果，可以将划分为2个部分，一部分是平方值小于等于x，另一部分则是大于x，如果mid落在左边部分，left = mid；如果mid落在右边部分，right = mid-1，接下来我们就直接套模版就好了

class Solution {public int mySqrt(int 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;}
}

题目4：搜索插入位置

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

解题思路：二段性如图，找出二段性后，根据left和right的变化直接套模版，但是需要处理一下实例3的情况，如果target都大于数组中最后一个元素，直接返回数组长度即可

class Solution {public int searchInsert(int[] nums, int target) {if (target > nums[nums.length - 1]) {return nums.length;}int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return left;}
}

题目5：山脉数组的峰顶索引

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

解题思路：

代码实现：

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

题目6：寻找峰值

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

二分查找：二段性如图所示

代码实现：

class Solution {public int findPeakElement(int[] nums) {int left = 0;int right = nums.length -1;while(left<right) {int mid = left + (right - left)/2;if(nums[mid]>nums[mid+1]) {right = mid;} else {left = mid+1;}}return left;}
}

题目7：寻找旋转数组中的最小值

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

解题思路：

题目要求的就是数组中的最小值

代码实现：

class Solution {public int findMin(int[] nums) {int left=0;int right =nums.length-1;while(left<right){int  mid = left + (right-left)/2;if(nums[mid]<nums[right]){right=mid;} else {left =mid +1;}}return nums[left];}
}

题目8：点名

LCR 173. 点名 - 力扣（LeetCode）

解题思路：

代码实现：

class Solution {public int takeAttendance(int[] records) {if (records.length == 1) {if (records[0] == 0) {return 1;}return records[0] - 1;}int left = 0;int right = records.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (mid == records[mid]) {left = mid + 1;} else {right = mid;}}if (records[left] == left) {return left + 1;}return left;}
}