算法模型总结:二分查找
文章目录
- 一、最基本的二分查找
- 1.二分查找的应用场景
- 2.二分查找核心书写思路
- 二、变式一:元素可以重复
- [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)
- 1.思路
- 2.具体实现
- 3.思考
- 三、变式二:非数组二分查找
- [69. x 的平方根 ](https://leetcode.cn/problems/sqrtx/)
- 1.思路
- 2.实现
- 四、小结
- 四、小结
一、最基本的二分查找
[704. 二分查找]
通过对基本的二分查找的分析,我们可以总结变式的来源。
1.二分查找的应用场景
1.数组是有序的。
2.数组中的元素不重复。
所谓查找,本质就是每一次排除一批数据。因此往往也伴随着需要分类讨论。
2.二分查找核心书写思路
-
首先需要处理要查找的元素在数组范围外的部分,即没有找到。
-
然后在数组中进行二分查找。
-
[left,right]:区间为left和right,其中它们都是数组下标。
-
while(left<=right):这是因为下标为left=right的这个数据还没有参与比较。
-
if(target<mid) left=mid+1:这是因为mid值已经参与比较了,而且使用的是闭区间。
class Solution {
public:
int search(vector<int>& nums, int target) {
if(target<nums[0]||target>nums[nums.size()-1])
{
return -1;
}
else
{
int left=0;
int right=nums.size()-1;
while(left<=right)
{
int mid=(left+right)/2;
if(target<nums[mid])
{
right=mid-1;
}
else if(target>nums[mid])
{
left=mid+1;
}
else
{
return mid;
}
}
return -1;
}
}
};
二、变式一:元素可以重复
34. 在排序数组中查找元素的第一个和最后一个位置
1.思路
该变式没有完全改变有序的特性,依然是进行查找,因此还是可以使用二分查找的。
-
还是进行分类讨论,即先处理在数组之外的情况。
-
再在数组内部进行二分查找寻找左右边界。
寻找边界的关键在于,当每一次比较后的left和right如何进行处理。
这里以左边界为例:
当target<nums[mid]的时候,显然无论元素是否重复在mid的右边都没有target值,因此right=mid-1;
当target>nums[mid]的时候,显然无论元素是否有重复mid的左边都没有target值,因此left=mid+1;
当target=nums[mid]的时候,由于是寻找左边界,因此不关心mid右边是否有重复的值,但是左边依然有可能有重复的值,因此right=mid-1。
而最终while循环终止的时候,一定是right=left-1,所以right+1即left,就是左边界。
2.具体实现
class Solution {
public:
int FindLeftBorder(vector<int>& nums,int target,int left,int right)
{
while(left<=right)
{
int mid=(right+left)/2;
if(target>nums[mid])
{
left=mid+1;
}
else
{
right=mid-1;
}
}
if(nums[right+1]==target)
{
return right+1;
}
else
{
return -1;
}
}
int FindRightBorder(vector<int>& nums,int target,int left,int right)
{
while(left<=right)
{
int mid=(right+left)/2;
if(target<nums[mid])
{
right=mid-1;
}
else
{
left=mid+1;
}
}
if(nums[left-1]==target)
{
return left-1;
}
else
{
return -1;
}
}
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> v;
v.resize(2);
if(nums.size()==0)
{
v[0]=-1;
v[1]=-1;
return v;
}
if(target<nums[0])
{
v[0]=-1;
v[1]=-1;
return v;
}
else if(target>=nums[0]&&target<=nums[nums.size()-1])
{
int left=0;
int right=nums.size()-1;
int rightborder=FindRightBorder(nums,target,left,right);
int leftborder=FindLeftBorder(nums,target,left,right);
v[0]=leftborder;
v[1]=rightborder;
return v;
}
else
{
v[0]=-1;
v[1]=-1;
return v;
}
}
};
3.思考
关键点就在于二分查找的最后结果是落在left=right的情况下,查找边界与简单的二分查找的区别就在于如何处理target=nums[mid]使得当最终left=right的时候,left或者right是一个边界。显然每一次都是对mid+1或者-1操作来缩小查找范围,可以从这里进行思考怎么处理。
三、变式二:非数组二分查找
69. x 的平方根
1.思路
思路主要在于,怎么识别它是一个二分查找。其实还是满足以上两个条件,即无重复元素,数组有序。
求x的平方根,即在x之前的数据中寻找x的平方根。
2.实现
class Solution {
public:
int mySqrt(int x) {
int left=1;
int right=x;
while(left<=right)
{
int mid=left+(right-left)/2;
if(mid<(x/mid))
{
if(mid+1>(x/(mid+1)))
{
return mid;
}
left=mid+1;
}
else if(mid>(x/mid))
{
if((mid-1)<(x/(mid-1)))
{
return mid-1;
}
right=mid-1;
}
else
{
return mid;
}
}
return 0;
}
};
注意,这里要使用除法而不能是乘法,有可能出现越界的情况。同时为了避免越界,使用的是left+(right-left)/2的方式来寻找mid。
四、小结
识别二分查找:元素有序,进行查找
处理二分查找:明确结束循环的两种方式,即找到了或者left=right+1等去情况,查找元素使用前者,查找边界使用后者。
思考:通过处理当target=nums[mid]的时候的left和right值来进行切入。
本文将持续更新
,使用的是left+(right-left)/2的方式来寻找mid。
四、小结
识别二分查找:元素有序,进行查找
处理二分查找:明确结束循环的两种方式,即找到了或者left=right+1等去情况,查找元素使用前者,查找边界使用后者。
思考:通过处理当target=nums[mid]的时候的left和right值来进行切入。
本文将持续更新