【LeetCode】二分查找精选10题
LeetCode 二分查找精选10题 详解
目录
第2题“搜索插入位置”必看，讲解了二段式二分查找循环条件为什么是left < right和中点什么时候取靠左的什么时候取靠右的。
二分查找（Binary Search）也称折半查找，要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分查找算法每次将查找范围减少一半，因此对于一个长度为n的数组可能需要O(logn)次查找，每次查找只需要比较当前查找范围的中间数字和目标数字，在O(1)的时间可以完成，因此二分查找算法的时间复杂度是O(logn)。
在一个1~10的有序数组中查找数字7示意图：
二分查找法常用来在排序数组中查找和在一个数值范围内查找。
在排序数组中二分查找：
1. 二分查找（简单）
- 如果nums[mid] < target，那么target一定在[mid + 1, right]区间内
- 如果nums[mid] > target，那么target一定在[left, mid - 1]区间内
- 如果nums[mid] = target，找到target
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n - 1;
while (left <= right)
{
int mid = (left + right) / 2;
// 如果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. 搜索插入位置（简单）
- 如果nums[mid] < target，那么pos一定在[mid + 1, right]区间内
- 如果nums[mid] >= target，那么pos一定在[left, mid]区间内
二段式二分查找一定要注意细节：
细节1：循环条件为left < right，不是left <= right。
right不管怎么移动都是在[pos, n - 1]区间内，当left == right时，left、right、mid都是同一位置。如果left == right时进入循环，nums[mid] 一定>= target，执行right = mid，实际上right根本没动，整个区间都没动，进入下一次循环，还会执行相同的步骤，显然出现了死循环。
其实left == right时就唯一确定了一个元素，如果== target，说明数组中存在target，left或right就是target的下标，如果!= target，说明数组中不存在target，left或right就是target的插入位置。
细节2：如果区间大小是偶数，中点取靠左的，即mid = left + (right - left) / 2。
规律：
细节3：如果数组所有元素全> target，插入位置为0，这种情况不用特殊处理。如果数组所有元素全< target，最后left == right时，定位的是数组最后一个元素（nums[n-1]），这时不能返回left或right，应该返回n。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n - 1;
while (left < right)
{
int mid = left + (right - left) / 2; // 中点取靠左的
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return nums[left] < target ? n : left;
}
};3. 点名（简单）
- 如果records[mid] == mid，那么pos一定在[mid + 1, right]区间内
- 如果nums[mid] > mid，那么pos一定在[left, mid]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠左的，即mid = left + (right - left) / 2。
细节3：如果所有元素都等于其下标，说明缺的是最后一个数，这时不能返回left或right，应该返回n - 1，这里n指的不是数组的大小，指的是一共有几个同学，n - 1是最后一个学号。
class Solution {
public:
int takeAttendance(vector<int>& records) {
int sz = records.size(); // 数组大小
int n = sz + 1; // n位同学
int left = 0;
int right = sz - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (records[mid] == mid)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return records[left] == left ? n - 1 : left;
}
};4. 在排序数组中查找元素的第一个和最后一个位置（中等）
查找左边界lpos：
- 如果nums[mid] < target，那么lpos一定在[mid + 1, right]区间内
- 如果nums[mid] >= target，那么lpos一定在[left, mid]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠左的，即mid = left + (right - left) / 2。
细节3：left == right时定位的元素不一定是target，因为target可能不在数组中。
查找右边界lpos：
- 如果nums[mid] <= target，那么lpos一定在[mid, right]区间内
- 如果nums[mid] > target，那么rpos一定在[left, mid - 1]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠右的，即mid = left + (right - left + 1) / 2。
细节3：这里不用判断left == right时定位的元素是不是target，因为既然执行到这里了，说明已经找到了左边界，那么target一定存在。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0)
return { -1,-1 };
// 查找左边界
int left = 0;
int right = n - 1;
while (left < right)
{
int mid = left + (right - left) / 2; // 中点取靠左的
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid;
}
}
// 判断确定出来的元素是不是target，如果不是，说明数组中不存在target
if (nums[left] != target)
{
return { -1,-1 };
}
int lpos = left; // 标记左边界
// 查找右边界
left = 0;
right = n - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2; // 中点取靠右的
if (nums[mid] > target)
{
right = mid - 1;
}
else
{
left = mid;
}
}
int rpos = right; // 标记右边界
return { lpos,rpos };
}
};5. 山脉数组的峰顶索引（中等）
- 如果arr[mid] > arr[mid - 1]，即mid在递增区间内，那么pos一定在[mid, right]区间内
- 如果arr[mid] < arr[mid - 1]，即mid在递减区间内，那么pos一定在[left, mid - 1]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠右的，即mid = left + (right - left + 1) / 2。
细节3：第一个元素和最后一个元素都不可能是峰顶，查找范围为[1, n - 2]。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
int left = 1;
int right = n - 2;
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[mid] > nums[mid - 1]，即mid在递增区间内，那么pos一定在[mid, right]区间内
- 如果nums[mid] < nums[mid - 1]，即mid在递减区间内，那么pos一定在[left, mid - 1]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠右的，即mid = left + (right - left + 1) / 2。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n = nums.size();
int left = 0;
int right = n - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (nums[mid] > nums[mid - 1])
{
left = mid;
}
else
{
right = mid - 1;
}
}
return left;
}
};7. 寻找旋转排序数组中的最小值（中等）
- 如果nums[mid] > nums[n - 1]，即mid在前半段区间内，那么pos一定在[mid + 1, right]区间内
- 如果nums[mid] <= nums[n - 1]，即mid在后半段区间内，那么pos一定在[left, mid]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠左的，即mid = left + (right - left) / 2。
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int left = 0;
int right = n - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > nums[n - 1])
{
left = mid + 1;
}
else
{
right = mid;
}
}
return nums[left];
}
};8. 有序数组中的单一元素（中等）
异或解法仍然有效，时间复杂度O(n)。既然是数组是有序的，可以考虑二分查找法。
将元素两两分为一组，只出现一次的元素是第一个两个元素不相同的组的第一个元素。
n（n为奇数）个元素可以分为n / 2 + 1个组，编号为0 ~ n / 2。
本题二分查找的单位是组，left、right、mid都指的是组的编号。
mid组第一个元素的下标记为i，i = mid * 2。
- 如果nums[i] == nums[i + 1]，那么pos所在的组一定在[mid + 1, right]区间内
- 如果nums[i] != nums[i + 1]，那么pos所在的组一定在[left, mid]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠左的，即mid = left + (right - left) / 2。
细节3：最后一个组没法比较两个元素，所以不参与查找，所以当数组只有1个元素时直接返回它。
细节4：如果最后left == right时定位的组的两个元素相同，说明数组最后一个元素才是只出现一次的元素。
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n = nums.size();
if (n == 1)
return nums[0];
int left = 0; // 第一个组的编号
int right = n / 2 - 1; // 倒数第二个组的编号
while (left < right)
{
int mid = left + (right - left) / 2;
int i = mid * 2; // mid组第一个元素的下标
if (nums[i] == nums[i + 1])
{
left = mid + 1;
}
else
{
right = mid;
}
}
int i = left * 2; // 最后定位的组第一个元素的下标
return nums[i] == nums[i + 1] ? nums[n - 1] : nums[i];
}
};在数值范围内二分查找：
1. x 的平方根（简单）
假设x为正数，其平方根的范围为[1, x]。
root * root <= x
- 如果mid * mid <= x，那么root一定在[mid, right]区间内
- 如果mid * mid > x，那么root一定在[left, mid - 1]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠右的，即mid = left + (right - left + 1) / 2。
细节3：0的平方根是0。
class Solution {
public:
int mySqrt(int x) {
if (x == 0)
return 0;
int left = 1;
int right = x;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (mid <= x / mid) // 数学上等价于mid*mid<=x，但是写mid*mid可能会溢出
{
left = mid;
}
else
{
right = mid - 1;
}
}
return left;
}
};2. 爱吃香蕉的珂珂（中等）
珂珂每小时至少吃1根香蕉。由于她每个小时只会选择1堆香蕉，所以她每小时吃香蕉的最大数目就是最大一堆香蕉的数目，记为high。
k表示珂珂在h小时内吃掉所有香蕉的最小速度。
设计一个函数getHours(vector<int>& piles, int speed)，计算以speed速度吃香蕉，需要多少小时吃完。速度越快，时间越少。
- 如果getHours(piles, mid) > h，k一定在[mid + 1, right]区间内
- 如果getHours(piles, mid) <= h，k一定在[left, mid]区间内
细节1：循环条件为left < right，不是left <= right。
细节2：如果区间大小是偶数，中点取靠左的，即mid = left + (right - left) / 2。
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int n = piles.size();
int high = 0; // 表示吃香蕉的最快速度
for (auto& i : piles)
{
high = max(high, i);
}
int left = 1;
int right = high;
while (left < right)
{
int mid = left + (right - left) / 2;
if (getHours(piles, mid) > h)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return left;
}
private:
int getHours(vector<int>& piles, int speed)
{
int hours = 0;
for (auto& i : piles)
{
hours += i / speed;
if (i % speed > 0)
{
hours++;
}
}
return hours;
}
};
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
9
0- 0
已为社区贡献6条内容
所有评论(0)