算法与数据结构学习笔记:二分法

本文最后更新于:November 28, 2021 am

二分搜索模板

给一个有序数组和目标值,找第一次/最后一次/任何一次出现的索引,如果没有出现返回-1

模板四点要素

  • 1、初始化:start=0、end=len-1
  • 2、循环退出条件:start + 1 < end
  • 3、比较中点和目标值:A[mid] ==、 <、> target
  • 4、判断最后两个元素是否符合:A[start]、A[end] ? target

注意:为了防止overflow,超过int范围,左中位数(a+b)=a+(b-a)/2,右中位数(a+b)=a+(b-a+1)/2如果有mid*mid,mid用int注意溢出

时间复杂度 O(logn),使用场景一般是有序数组的查找

典型示例

704. 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int search(vector<int>& nums, int target) {
int start,mid,end;
start=0;
end=nums.size()-1;

while(start<=end)
{
mid=start+(end-start)/2;//防止两数之和超过int范围
if(nums[mid]==target)
return mid;
if(nums[mid]>target)
{
end=mid-1;
}
else{
start=mid+1;
}


}
return -1;

}
};

大部分二分查找类的题目都可以用这个模板,然后做一点特殊逻辑即可

另外二分查找还有一些其他模板如下文,大部分场景模板#3 都能解决问题,而且还能找第一次/最后一次出现的位置,应用更加广泛

img

所以用模板#3 就对了

模板 #1 (left <= right)

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定(或使用它周围的特定元素)。
不需要后处理,因为每一步中,你都在检查是否找到了元素。如果到达末尾,则知道未找到该元素。

模板 #2 (left < right)

一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件,并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。 当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。

模板 #3 (left + 1 < right)

实现二分查找的另一种方法。
搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。 当剩下 2 个元素时,循环 / 递归结束。 需要评估其余元素是否符合条件。

如果是最简单的二分搜索,不需要找第一个、最后一个位置、或者是没有重复元素,可以使用模板#1,代码更简洁

总结

二分搜索核心四点要素(必背&理解)

  • 1、初始化:start=0、end=len-1
  • 2、循环退出条件:start + 1 < end
  • 3、比较中点和目标值:A[mid] ==、 <、> target
  • 4、判断最后两个元素是否符合:A[start]、A[end] ? target

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!