算法笔记(二)——二分查找算法
二分查找(Binary Search)是一种在有序数组中查找特定元素的算法。该算法的基本思想是通过每一次比较,将查找范围缩小一半,最终找到目标元素或者确定目标元素不存在。
步骤:
- 初始化两个指针````````和
r
分别指向区间的开始和终点; while(l< r)
计算中点mid = (l+ r)/ 2
(有溢出的风险),防止溢出的方法mid = (r- l) / 2 + l
- 判断
mid
处是否满足条件; - 如果目标元素等于中间元素,查找成功,返回中间元素的索引。
- 如果目标元素小于中间元素,说明目标元素可能在左半部分,更新
r= mid - 1
- 如果目标元素大于中间元素,说明目标元素可能在右半部分,更新
l= mid + 1
优势:
- 因为每次可以减少一半的查询量,所以时间复杂度低,为
O(logN)
条件:
- 数组必须有序;
版本1:
当我们将区间[l, r]
划分成[l, mid]
和[mid + 1, r]
时,其更新操作是r = mid
或者l = mid + 1
;,计算mid
时不需要加1。
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
版本2
当我们将区间[l, r]
划分成[l, mid - 1]
和[mid, r]
时,其更新操作是r = mid - 1
或者l = mid
;,此时为了防止死循环,计算mid
时需要加1。
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
二分查找
题目链接:二分查找
思路:
- 最基础的二分,按照上述步骤写即可;
C++代码
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int l = 0, r = nums.size() - 1;
while(l <= r)
{
int mid = l + r >> 1;
if(nums[mid] > target)
{
r = mid - 1;
}
else if(nums[mid] < target)
{
l = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
};
在排序数组中查找元素的第一个和最后一个位置
思路:
- 题目说明时间复杂度为
O(logN)
即让我们使用二分 - 判断数组是否为空,如果为空,则直接返回 {-1, -1},表示目标元素不存在于数组中
- 二分两次分别找左端点、右端点
寻找左端点
以左边界划分的两个区间的特点
左边区间的特点
[left, begin - 1]
都是小于x
的右边区间(包括左边界)
[begin, right]
都是⼤于等于x
的当
mid
落在[left, begin - 1]
的时候,也就是nums[mid] < target
;说明[left, mid]
都是可以舍去的,此时更新left
到mid + 1
的位置,继续在[mid + 1, right]
上寻找左边界当
mid
落在[begin , right]
的时候,也就是nums[mid] >= target
;说明[mid + 1, right]
都是可以舍去的,此时更新right
到mid
的位置,继续在[left, mid ]
上寻找左边界寻找右端点同理;
C++代码:
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
if(!nums.size()) return {-1,-1}; // 特判空数组
int begin = 0;
// 左端点;
int left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = (left + right) >> 1;
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(left < right)
{
int mid = left + right + 1>> 1;
if(nums[mid] <= target) left = mid;
else right = mid - 1;
}
return {begin, right};
}
};
搜索插入位置
题目链接:搜索插入位置
思路:
题目说明时间复杂度为
O(logN)
即让我们使用二分特判,如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
if(target > nums[nums.size() - 1]) return nums.size();
定义两指针
left
和right
,进入循环while(left < right)
通过计算中间位置
mid
(避免整数溢出的写法),对比中间元素与目标元素的大小关系,从而缩小查找范围若
nums[mid] < target
,则更新left = mid + 1
若
nums[mid] > target
,则更新right = mid
最后判断
nums[left]
与target
的关系
C++代码:
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// 如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
if(target > nums[nums.size() - 1]) return nums.size();
int left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = (left + right) / 2;
if(nums[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
};
x 的平方根
题目连接: x 的平方根
暴力思路:
- 依次枚举
[0, x]
中的所有数i
- 如果
i * i == x
,则返回i
- 如果
i * i > x
, 则返回i - 1
C++代码:
class Solution {
public:
int mySqrt(int x) {
for(int i = 0; i <= x; i++)
{
if(i * i == x) return i;
if(i * i > x) return i - 1;
}
return -1;
}
};
由于两个较⼤的数相乘可能会超过 int 最⼤范围, 所以用long long
class Solution {
public:
int mySqrt(int x) {
for(long long i = 0; i <= x; i++)
{
if(i * i == x) return i;
if(i * i > x) return i - 1;
}
return -1;
}
};
山脉数组的峰顶索引
题目链接:山脉数组的峰顶索引
思路:
- 如果
mid
位置呈现上升趋势,说明我们接下来要在[mid + 1, right]
区间继续搜索 - 如果
mid
位置呈现下降趋势,说明我们接下来要在[left, mid - 1]
区间继续搜索 - 如果
mid
位置就是⼭峰,直接返回结果
C++代码:
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1]) left = mid;
else right = mid - 1;
}
return left;
}
};
寻找峰值
题目链接:寻找峰值
思路:
- 如果
nums[mid] < nums[mid + 1]
,说明峰值可能在右半部分,更新left = mid + 1
- 如果
nums[mid] >= nums[mid + 1]
,说明峰值可能在左半部分,更新right = mid
- 循环直到
left >= right
,此时left 或 right
就是无序数组的峰值。返回left
C++代码:
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left=0, right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < nums[mid + 1]) left = mid + 1;
else right = mid;
}
return left;
}
};
寻找旋转排序数组中的最小值
题目链接:寻找旋转排序数组中的最小值
思路:
题⽬中的数组规则如下图所⽰
c点即为所求,由图可知A,B严格大于C,D>=C;
- 初始
left
和right
, - 当
mid
落在A,B时,即nums[mid] > D
,则更新left= mid + 1
- 当
mid
落在C,D时,即nums[mid] <= D
,则更新right = mid
C++代码:
class Solution {
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = left + right >> 1;
if(nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}
};