一、什么是二分查找
二分查找也称折半查找,是在一组有序(升序/降序)的数据中查找一个元素,它是一种效率较高的查找方法。
二、二分查找的原理
1、查找的目标数据元素必须是有序的。没有顺序的数据,二分法就失去意义。
2、数据元素通常是数值型,可以比较大小。
3、将目标元素和查找范围的中间值做比较(如果目标元素=中间值,查找结束),将目标元素分到较大/或者较小的一组。
4、通过分组,可以将查找范围缩小一半。
5、重复第三步,直到目标元素=新的范围的中间值,查找结束。
三、二分查找模板
1、朴素二分查找模板
2、一般二分查找模板
四、二分查找经典OJ题
4、1 二分查找
704. 二分查找 – 力扣(LeetCode)
1、题目描述
2、算法思路
a. 定义 left , right 指针,分别指向数组的左右区间。 b. 找到待查找区间的中间点 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 过程;c. 当 left 与 right 错开时,说明整个区间都没有这个数,返回 -1 。
3、算法代码
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;
}
};
4、2 在排序数组中查找元素的第⼀个和最后⼀个位置
34. 在排序数组中查找元素的第一个和最后一个位置 – 力扣(LeetCode)
1、题目描述:
2、算法思路:
⽤的还是⼆分思想,就是根据数据的性质,在某种判断条件下将区间⼀分为⼆,然后舍去其中⼀个 区间,然后再另⼀个区间内查找; ⽅便叙述,⽤ x 表⽰该元素, resLeft 表⽰左边界, resRight 表⽰右边界。
寻找左边界: ◦ 我们注意到以左边界划分的两个区间的特点: ▪ 左边区间 [left, resLeft – 1] 都是⼩于 x 的; ▪ 右边区间(包括左边界) [resLeft, right] 都是⼤于等于 x 的; • 因此,关于 mid 的落点,我们可以分为下⾯两种情况: ◦ 当我们的 mid 落在 [left, resLeft – 1] 区间的时候,也就是 arr[mid] < target 。说明 [left, mid] 都是可以舍去的,此时更新 left 到 mid + 1 的位置, 继续在 [mid + 1, right] 上寻找左边界; ◦ 当 mid 落在 [resLeft, right] 的区间的时候,也就是 arr[mid] >= target 。 说明 [mid + 1, right] (因为 mid 可能是最终结果,不能舍去)是可以舍去的,此时 更新 right 到 mid 的位置,继续在 [left, mid] 上寻找左边界; • 由此,就可以通过⼆分,来快速寻找左边界;
注意:这⾥找中间元素需要向下取整。 因为后续移动左右指针的时候: • 左指针: left = mid + 1 ,是会向后移动的,因此区间是会缩⼩的; • 右指针: right = mid ,可能会原地踏步(⽐如:如果向上取整的话,如果剩下 1,2 两个元 素, left == 1 , right == 2 , mid == 2 。更新区间之后, left,right,mid 的 值没有改变,就会陷⼊死循环)。 因此⼀定要注意,当 right = mid 的时候,要向下取整。
寻找右边界思路: ◦ ⽤ resRight 表⽰右边界; ◦ 我们注意到右边界的特点: ▪ 左边区间 (包括右边界) [left, resRight] 都是⼩于等于 x 的; ▪ 右边区间 [resRight+ 1, right] 都是⼤于 x 的; • 因此,关于 mid 的落点,我们可以分为下⾯两种情况: ◦ 当我们的 mid 落在 [left, resRight] 区间的时候,说明 [left, mid – 1](mid 不可以舍去,因为有可能是最终结果) 都是可以舍去的,此时更新 left 到 mid 的位置; ◦ 当 mid 落在 [resRight+ 1, right] 的区间的时候,说明 [mid, right] 内的元素 是可以舍去的,此时更新 right 到 mid – 1 的位置; • 由此,就可以通过⼆分,来快速寻找右边界;
注意:这⾥找中间元素需要向上取整。 因为后续移动左右指针的时候: • 左指针: left = mid ,可能会原地踏步(⽐如:如果向下取整的话,如果剩下 1,2 两个元 素, left == 1, right == 2,mid == 1 。更新区间之后, left,right,mid 的值 没有改变,就会陷⼊死循环)。 • 右指针: right = mid – 1 ,是会向前移动的,因此区间是会缩⼩的; 因此⼀定要注意,当 right = mid 的时候,要向下取整。
3、算法代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
int begin=0;
if(nums.size()==0) return {-1,-1};
int left=0,right=nums.size()-1;
while(right>left) //找左端点
{
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
if(nums[left]!=target) return {-1,-1};
else begin=left;
left=0,right=nums.size()-1;
while(right>left)
{
int mid=left+(right-left+1)/2;
if(nums[mid]<=target) left=mid;
else right=mid-1;
}
return {begin,right};
}
};
4、3 搜索插入位置
35. 搜索插入位置 – 力扣(LeetCode)
1、题目描述
2、算法思路
a. 分析插⼊位置左右两侧区间上元素的特点: 设插⼊位置的坐标为 index ,根据插⼊位置的特点可以知道: • [left, index – 1] 内的所有元素均是⼩于 target 的; • [index, right] 内的所有元素均是⼤于等于 target 的。 b. 设 left 为本轮查询的左边界, right 为本轮查询的右边界。根据 mid 位置元素的信息,分析下⼀轮查询的区间: ▪ 当 nums[mid] >= target 时,说明 mid 落在了 [index, right] 区间上, mid 左边包括 mid 本⾝,可能是最终结果,所以我们接下来查找的区间在 [left, mid] 上。因此,更新 right 到 mid 位置,继续查找。 ▪ 当 nums[mid] < target 时,说明 mid 落在了 [left, index – 1] 区间上, mid 右边但不包括 mid 本⾝,可能是最终结果,所以我们接下来查找的区间在 [mid + 1, right] 上。因此,更新 left 到 mid + 1 的位置,继续查找。 c. 直到我们的查找区间的⻓度变为 1 ,也就是 left == right 的时候, left 或者 right 所在的位置就是我们要找的结果。
3、算法代码
class Solution {
public:
int searchInsert(vector<int>& nums, int target)
{
int left=0,right=nums.size()-1;
while(right>left)
{
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
if(nums[left]<target) return right+1;
return right;
}
};
4、4 X的平方根
69. x 的平方根 – 力扣(LeetCode)
1、题目描述
2、算法思路
依次枚举 [0, x] 之间的所有数 i : (这⾥没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回 了,往后的情况就不会再判断。反⽽研究枚举区间,既耽误时间,⼜可能出错) ▪ 如果 i * i == x ,直接返回 x ; ▪ 如果 i * i > x ,说明之前的⼀个数是结果,返回 i – 1 。 由于 i * i 可能超过 int 的最⼤值,因此使⽤ long long 类型
3、算法代码
class Solution {
public:
int mySqrt(int x)
{
if(x<1) return 0;
int left=1,right=x;
while(right>left)
{
long long mid=left+(right-left+1)/2;
if(mid*mid>x) right=mid-1;
else left=mid;
}
return left;
}
};
4、5 山峰数组的峰顶
852. 山脉数组的峰顶索引 – 力扣(LeetCode)
1、题目描述
2、算法思路
峰顶的特点:⽐两侧的元素都要⼤。 因此,我们可以遍历数组内的每⼀个元素,找到某⼀个元素⽐两边的元素⼤即可3、算法代码
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr)
{
for(int i=1;i<arr.size()-1;i++)
{
if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
{
return i;
}
}
return 0;
}
};
4、5 寻找峰值
162. 寻找峰值 – 力扣(LeetCode)
1、题目描述
2、算法思路寻找⼆段性:
任取⼀个点 i ,与下⼀个点 i + 1 ,会有如下两种情况: • arr[i] > arr[i + 1] :此时「左侧区域」⼀定会存在⼭峰(因为最左侧是负⽆穷),那么我们可以去左侧去寻找结果; • arr[i] < arr[i + 1] :此时「右侧区域」⼀定会存在⼭峰(因为最右侧是负⽆穷),那么我们可以去右侧去寻找结果。 当我们找到「⼆段性」的时候,就可以尝试⽤「⼆分查找」算法来解决问题。 3、算法代码
class Solution {
public:
int findPeakElement(vector<int>& nums)
{
vector<int> ret;
int left=0,right=nums.size()-1;
while(right>left)
{
int mid=left+(right-left+1)/2;
if(nums[mid]>nums[mid-1]) left=mid;
else right=mid-1;
}
return left;
}
};
4、6 寻找旋转排序数组中的最⼩值
153. 寻找旋转排序数组中的最小值 – 力扣(LeetCode)
1、题目描述
2、算法思路
题⽬中的数组规则如下图所示:
其中 C 点就是我们要求的点。 ⼆分的本质:找到⼀个判断标准,使得查找区间能够⼀分为⼆。 通过图像我们可以发现, [A,B] 区间内的点都是严格⼤于 D 点的值的, C 点的值是严格⼩于 D 点的值的。但是当 [C,D] 区间只有⼀个元素的时候, C 点的值是可能等于 D 点的值的。 因此,初始化左右两个指针 left , right :然后根据 mid 的落点,我们可以这样划分下⼀次查询的区间: ▪ 当 mid 在 [A,B] 区间的时候,也就是 mid 位置的值严格⼤于 D 点的值,下⼀次查询区间在 [mid + 1,right] 上; ▪ 当 mid 在 [C,D] 区间的时候,也就是 mid 位置的值严格⼩于等于 D 点的值,下次查询区间在 [left,mid] 上。 当区间⻓度变成 1 的时候,就是我们要找的结果。
3、算法代码
class Solution {
public:
int findMin(vector<int>& nums)
{
int tmp=nums[nums.size()-1];
int left=0,right=nums.size()-1;
while(right>left)
{
int mid=left+(right-left)/2;
if(nums[mid]>tmp) left=mid+1;
else right=mid;
}
return nums[left];
}
};
4、7 0~n-1缺失的数字
LCR 173. 点名 – 力扣(LeetCode)
1、题目描述
2、算法思路
关于这道题中,时间复杂度为 O(N) 的解法有很多种,⽽且也是⽐较好想的,这⾥就不再赘述。 本题只讲解⼀个最优的⼆分法,来解决这个问题。 在这个升序的数组中,我们发现: ▪ 在第⼀个缺失位置的左边,数组内的元素都是与数组的下标相等的; ▪ 在第⼀个缺失位置的右边,数组内的元素与数组下标是不相等的。 因此,我们可以利⽤这个「⼆段性」,来使⽤「⼆分查找」算法。
3、算法代码
class Solution {
public:
int takeAttendance(vector<int>& records)
{
int left=0,right=records.size()-1,k=0;
while(right>left)
{
int mid = left+(right-left)/2;
if(records[mid]!=mid) right=mid;
else left=mid+1;
}
return left==records[left]?left+1:left;
}
版权声明:本文为博主作者:#欲速则不达#原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/m0_69323023/article/details/135323432