二分查找算法简介
1. 首先说明二分查找算法是比较恶心, 细节很多, 很容易写出死循环的算法, 但熟悉了之后是最简单的算法.
2. 其次我们可能听说过二分查找的前提是数组有序的前提下进行, 但其实不一定.
3. 二分查找算法有一套模板:
- 朴素的二分模板: 比较简单, 但是有局限性
- 查找左边界的二分模板, 查找右边界的二分模板: 万能模板, 但是细节很多.
二分查找算法的关键是"二段性" , 当我们发现一个规律, 根据这个规律能把这个数组分为两部分, 根据规律能有选择性的舍去一部分, 进而能在另一个部分继续查找, 可以看到这其中并没有提到数组是否有序, 关键在于数组是否有"二段性".
此外, 我们对于选择区间划分点mid的位置也并没有具体的描述必须选择在中间点, 三分之一点, 四分之一点....都可以, 因为只要我们找到的这个位置能把区间分为两部分即可, 即数组有二段性即可.
但是选择中间点作为划分点时间复杂度是最好的.
题目1: 二分查找
朴素二分查找的步骤:
a. 定义 left , right 指针, 分别指向数组的左右区间.
b. 找到待查找区间的中间点 mid , 找到之后分三种情况讨论：
朴素二分查找的核心:
1. arr[mid] == target 说明正好找到, 返回 mid 的值；
2. arr[mid] > target 说明 [mid, right] 这段区间都是大于 target 的，因此舍去右边区间, 在左边 [left, mid -1] 的区间继续查找，即让 right = mid -1 ，然后重复 2 过程;
3. arr[mid] < target 说明 [left, mid] 这段区间的值都是小于 target 的, 因此舍去左边区间, 在右边 [mid + 1, right] 区间继续查找, 即让 left = mid +1 , 然后重复 2 过程;
c. 当 left 与 right 错开时, 说明整个区间都没有这个数, 返回 -1 .
相关细节问题:
1. 循环结束的条件: left>right, 也就是这个区间不存在的时候, 说明没找到; 注意: 当left==right的时候循环没结束, 此时代表区间内只有一个数, 这个数也是要判断的.
2. 为什么时间复杂度低?
程序执行次数 1次 -> 区间长度n/2, 2次->n/2^2, 3次->n/2^3, ..., x次->n/2^x, 假设在第x次区间长度为1, 也就最坏的情况下找到了这个数, 那么n/2^x = 1 -> x = logn, 所以时间复杂度为O(logn).
class Solution {
public:
int search(vector<int>& nums, int target)
{
int left = 0, right = nums.size()-1;
while(left <= right)
{
// int mid = (left+right)/2;//加法有溢出的风险
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;//没找到
}
};关于朴素二分查找的模板:
while(left <= right)
{
int mid = left + (right-left)/2;
if(...)
left = mid + 1;
else if(...)
right = mid -1;
else
return ...;
}其中...根据题目所分析出的二段性进行填写. 其中两个细节:
1. 条件判断为left<=right.
2. 求中间点的方式为left +(right-left)/2防溢出.
3. 朴素二分查找求中间点用 left+(right-left)/2 和 left+(right-left+1)/2 没有差别, 这两种求中间点的方法在区间长度为奇数的时候, 求出的mid是一样的, 唯一的区别在于区间长度为偶数的时候, 第一种求出的mid偏左, 第二种求出的mid偏右, 对于朴素二分查找这两种没有区别.
题目2: 在排序数组中查找元素的第一个和最后一个位置
这道题用朴素二分法无法求解, 因为要求的是一个区间, 朴素二分求到的那个值无法确定位于区间的哪一个位置, 但是还是可以用二分的, 关键是找到数组的二段性:
1. 查找区间的左端点:
可以发现, 我们可以把区间按照大于等于target和小于target分为两部分:
当nums[mid]的值落在小于target的区间内时, 如何去更新值呢? 能去更新right吗?
不能, 因为区间左端点的位置在大于等于target的区间内, 更新right就错过了这个点, 所以要更新left, 而left左边区间的值包括left都小于target, 所以left = mid+1, 最好的情况就是left恰好在区间的右端, 此时mid对应的值就一定等于要找的那个位置.
当nums[mid]的值落在大于等于target的区间内时, 如何去更新right呢?
right不能等于mid-1, 因为如果mid恰好落在区间的左端点, 那么mid-1就错过了这个位置, 而right要尽可能的往左移取找到区间的左端点, 所以right=mid.
细节处理:
1. 循环条件必须是left<right, 而不能是left<=right, 因为当left==right的时候, 一定是要找的区间左端点, 如果条件还取判断是否相等, 就会陷入死循环.
2. 求中点的操作:
上面我们说了 left+(right-left)/2 和 left+(right-left+1)/2 两种取中点的方式, 这里必须要选择左边那种, 否则又会进入死循环, 因为当区间不断缩减并只剩两个元素的时候,
1. 假如存在区间左端点: 第二种取中点取的一定是right的值, 就会陷入死循环
2. 假如不存在区间: 假如区间内的值都大于target, right一直向左移动, 最终也会达到区间长度为2的, 和上面一样陷入死循环; 假如区间内的值都小于target, left一直向左移动, 最终不会死循环, 但是前面两种情况都会死循环.
2. 查找区间的右端点:
操作和查找区间左端点类似, 也是寻找二段性, 把区间分为小于等于target和大于target两部分, 和上面相反当mid落在小于等于target区间, left=mid, 落在大于3的区间, right = mid-1.
循环也是left < right, 但是取中点的方式必须是第二种, 道理和之前类似, 只剩两个元素时会进入死循环.
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
//处理边界情况
if(nums.empty())
return {-1,-1};
int begin = -1, end = -1;
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)
begin = left;
left = 0, right = nums.size()-1;//这里left可以不用重置, 因为left已经在begin位置
//寻找区间右端点
while(left < right)
{
int mid = left + (right-left+1)/2;
if(nums[mid] > target)
right = mid - 1;
else
left = mid;
}
if(nums[right] == target)
end = right;
return {begin,end};
}
};寻找区间左端点和右端点模板:
//寻找区间左端点
while(left < right)
{
int mid = left + (right-left)/2;
if(...)
left = mid+1;
else
right = mid;
} //寻找区间右端点
while(left < right)
{
int mid = left + (right-left+1)/2;
if(...)
right = mid - 1;
else
left = mid;
}...处根据二段性填入
这两种划分方式选择哪种呢?
根据题目去判断要找的值最终是 >=target or <=target的, 因为left和right相遇的位置一定是包含等于的那个区间, 所以要找的结果一定是要落在包含等于的区间内的.
题目3: 搜索插入位置
解法一: 朴素二分查找, 先用朴素二分查找看看是否能找到target, 能找到直接返回; 找不到的话, 如果循环结束前区间为1的值大于target, right向左移动, 此时的left就是要插入的位置, 如果小于target, left向右移动, left也是要插入的位置 , 所以返回left即可.
class Solution {
public:
int searchInsert(vector<int>& nums, int target)
{
int left = 0, right = nums.size()-1;
int mid;
while(left<=right)
{
mid = left +(right- left)/2;
if(nums[mid] < target)
left = mid+1;
else if(nums[mid] > target)
right = mid-1;
else
return mid;
}
return left;
}
};解法二: 二段性划分: 对于能找到target, 插入位置在数组中和插入位置在数组最左侧的情况, 要返回的位置要么是=target的位置, 要么是第一个大于target的位置, 所以把区间划分为 小于target和大于等于target两部分:
注意, 需要单独处理插入位置在最右边的, 此时整个数组都在小于target的区间, 最终一定是落在数组最后一个位置, 要将返回值+1.
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(target > nums[left])
return left+1;
else
return left;
}
};题目4: x的平方根
二分查找方法依然是去寻找数组的二段性, 要去[1,x]的数组中去寻找x的平方根, 可以把数组划分为平方<x和平方>=x 或 平方<=x和平方>x ,哪一种划分是正确的? 因为此题返回的是平方根的整数部分, 比如8的算术平方根是2.82842, 应该返回2, 返回的数值是<=实际的平方根的, 所以应该划分为平方<=x和平方>x.
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(target > nums[left])//单独处理插入在右边界
return left+1;
else
return left;
}
};题目5: 山峰数组的峰顶索引.
暴力解法:
对于数组每一个元素, 比较arr[i] > arr[i-1]是否成立, 出现的第一个不成立的位置记为k, 则k-1就是山峰位置.
二分查找:
观察山脉数组的定义, 可以发现对于山峰左侧包括山峰的位置, arr[i] > arr[i-1], 对于山脉的右侧, arr[i] < arr[i-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])
right = mid-1;
else
left = mid;
}
return left;
}
};题目6:寻找峰值
暴力解法:
1. 第一个位置后如果下降, 则第一个位置就是山峰
2. 第一个位置后上升, 遇到第一个arr[i] < arr[i-1]的位置, i-1即为山峰
3. 第一个位置到最后一直上升, 最后一个位置就是山峰.
二分查找:
此题和上一题类似, 但是可能有多个山峰, 也可能是一路上升或者一路下降, 但只需要找到一种情况即可:
arr[i] > arr[i-1]时, 修正left = mid; arr[i] < arr[i-1]时, 修正right = mid-1, 其实就算有多个山峰, 经过区间不断地缩小, 最终一定会变成上一题的只有一个山峰的情况, 无非多了两种一路上升和一路下降, 所以代码和上一题一模一样.
class Solution {
public:
int findPeakElement(vector<int>& nums)
{
int left = 0, right = nums.size()-1;
while(left < right)
{
int mid = left + (right-left+1)/2;
if(nums[mid] < nums[mid-1])
right = mid-1;
else
left = mid;
}
return left;
}
};题目7: 搜索旋转排序数组中的最小值
以这段数组为例, 以最小值为分界点, 左侧区间内的值一定大于D点的值, 右侧区间内的值一定小于等于D点的值, 根据这个性质就可以把数组分为两段, 题目变成求右区间的左端点:
class Solution {
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size()-1;
int end = right;
while(left < right)
{
int mid = left + (right-left)/2;
if(nums[mid] < nums[end])
right = mid;
else
left = mid+1;
}
return nums[left];
}
};如果我们用A点作为判断点, 左侧区间内的值都大于等于A点, 右侧区间内的值都小于A点, 可以吗?
不完全可以, 这种情况下需要单独去判断如果数组是否是完全递增的情况, 这时left会一直++直到最右侧, 此时是区间的最大值. 而用D点作为判断点则不用考虑这个情况.
class Solution {
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size()-1;
int end = right;
while(left < right)
{
int mid = left + (right-left)/2;
if(nums[mid] >= nums[0])
left = mid+1;
else
right = mid;
}
if(nums[end]-nums[0] > 0)
return nums[0];
return nums[left];
}
};题目8: 点名
此题以缺失的那个值作为分界点, 可以把区间划分为两块, 左区间内的值 下标 和 数组内对应的值 是相等的, 右区间 下标 和 数组内对应的值 是不相等的, 以此来将数组划分为两块. 需要注意, 如果最后求出来的返回值 下标 和 数组内对应的值 还是相等的, 说明缺失的是学号为n-1的那个人, 要返回left+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;
}
};此题还有若干时间复杂度为O(n)的方法:
1. 遍历数组哈希表存储出现次数, 没出现的就是缺失的
2. 直接遍历找结果
3. 位运算, 根据相同的数字异或等于0的性质, 将前n-1个数异或求和, 然后与数组中的数再异或, 最终的结果就是缺失的值
4. 等差数列求和, 求前n-1项的和再减去数组元素的和, 得到的就是缺失的值.
