算法专题三: 二分查找
目录
- 1. 朴素版: 二分查找
- 2. 查找排序数组元素第一个和最后一个位置
- 3. 搜索插入位置
- 4. x的平方根
- 5. 山脉数组的峰顶索引
- 6. 寻找旋转数组中的最小值
- 7. 点名
博客主页: 酷酷学!!!
感谢您的关注~
正文开始
1. 朴素版: 二分查找
题目思路: 仅需根据题意, 找出二段性, 正确更新下标位置即可.
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)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
else return mid;
}
return -1;
}
};
2. 查找排序数组元素第一个和最后一个位置
算法原理:
那么本道题朴素的二分查找就不适用了, 我们需要根据二段行将数组进行划分, 得到下图结论.
这里的注意事项细节处理, 循环条件以及我们的求中点操作, 那么为什么这种算法就是对呢?
下面我们可以通过三种情况来细分, 如果有结果则相遇位置就是结果, 如果全大于t, 则会一直right向左移动最后相遇位置结束, 退出循环, 全小于t, 则left会一直向右移动, 最后退出循环, 那么为什么求左端点第二种求中点操作死循环呢?
int mid = left + (right - left + 1)/2, 对于这种写法, 假设剩下最后两个元素, 这两区别无非就是一个拿到前一个元素, 一个拿到后一个元素, 如果我们要求左端点拿到后面的元素, 如果muns[mid] < target. left会变成mid+1, 出循环, 如果nums[mid] <= target,则right会一直等于mid的位置, 陷入死循环.
故, 求右端点类似
总结一下: 如何让二分从恶心变成easy~
编写代码:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty()) return {-1,-1};//处理为空的情况
int left = 0 ,right = nums.size() - 1;
int begin = 0, end = 0;
while(left < right)
{
int mid = left + (right - left)/2;
if(nums[mid] < target)
left = mid + 1;
else right = mid;
}
begin = left;
if(nums[left] != target) return {-1,-1}; //处理未找到的情况
right = nums.size() -1;
while(left < right)
{
int mid = left + (right - left + 1)/2;
if(nums[mid] <= target)
left = mid;
else right = mid - 1;
}
end = left;
return {begin,end};
}
};
3. 搜索插入位置
算法思路:
根据题目我们很容易发现二段性, 需要待插入的位置就为左端点, 注意, 如果所有数据都小于target则相遇位置为最后一个位置, 待插入位置为相遇位置的下一个位置.
编写代码:
class Solution {
public:
int searchInsert(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)
left = mid + 1;
else right = mid;
}
if(nums[left] < target) return left + 1;
return left;
}
};
4. x的平方根
算法思路:
我们根据题意不难找出二段性, 要查找的位置为右端点, 列出判断语句即可.
编写代码:
class Solution {
public:
int mySqrt(int x) {
long long left = 0, right = x;
while(left < right)
{
long long mid = left + (right - left + 1) / 2;
if(mid * mid <= x)
left = mid;
else right = mid - 1;
}
return left;
}
};
5. 山脉数组的峰顶索引
算法思路:
根据二段性, 分出左右数组, 注意如果判断语句中有-1, 则计算mid有+1.
编写代码:
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;
}
};
6. 寻找旋转数组中的最小值
算法思路:
以最后一个数为基准值进行比较, 即可将数组划分成两部分, 这里不可以以nums[0]进行划分, 因为当数组有序时, 相遇位置会在最后一个位置导致结果错误, 需要特殊处理.
编写代码:
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int left = 0, right = n - 1;
int x = nums[n - 1];
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] > x)
left = mid + 1;
else right = mid;
}
return nums[left];
}
};
以nums[0]为基准值划分
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
int x = nums[0];
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] >= x)
left = mid + 1;
else
right = mid;
}
if(nums[right] > x) return nums[0];
else return nums[left];
}
};
7. 点名
算法思路:
本道题解法多种, 但是二分查找时间复杂度最低, 根据题目不难发现根据下标即可划分出数组, 但是注意判断, 当数组有序时, 缺失位置为最后一个位置的下一个位置, 这里指针相遇的位置需要最后+1.
编写代码:
class Solution {
public:
int takeAttendance(vector<int>& records) {
int left = 0, right = records.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(records[mid] == mid)
left = mid + 1;
else right = mid;
}
if(records[left] == left) return left + 1;
return left;
}
};
完, 感谢点赞收藏!!!