我要成为算法高手-二分查找篇
目录
- 题目1：二分查找
- 总结朴素二分模版
- 题目2：在排序数组中查找元素的第一个和最后一个位置
- 总结二分模版
- 题目3：x的平方根
- 题目4：搜索插入位置
- 题目5：山脉数组的峰顶索引
- 题目6：寻找峰值
- 题目7：寻找旋转数组中的最小值
- 题目8：点名
当数组具有二段性时，可以使用二分查找，二分查找是什么？二段性又是什么？请看题目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=right
if(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;
}
}