二分查找习题篇(上)
二分查找习题篇(上)
1.二分查找
题目描述：
给定⼀个 n 个元素有序的（升序整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
解法一：暴力解法
从前往后枚举每一个元素，将其与目标值进行对比。
时间复杂度最差为O(N)。
解法二：二分查找算法
当数组具有“二段性”时，我们就可以用二分查找算法。
算法思路：
定义 left ， right 指针，分别指向数组的左右区间。
当left<=right时，下列一直循环：
找到待查找区间的中间点 mid ，找到之后分三种情况讨论：
- arr[mid] == target：返回 mid 的值；
- arr[mid] > target：让 right = mid - 1，在 [left, right] 的区间继续查找 ,重复 2 过程；
- arr[mid] < target：让 left = mid + 1, 在 [left, right] 的区间继续查找，重复 2 过程；
- 当left>right时，说明整个区间都没有这个数，返回 -1 。
细节问题：
1.循环结束的条件
当left>right
2.为什么是正确的？
二分查找是从暴力解法优化而来的
3.时间复杂度
1次——>n/21=n/2
2次——>n/22=n/4
3次——>n/23=n/8
…次——>…
x次——>n/2x=1(当left==right，找到要找的元素时)
2x=n——>x=logN
因此，二分查找的时间复杂度是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-left)/2; //防止溢出
if(nums[mid]>target) right=mid-1;
else if(nums[mid]<target) left=mid+1;
else return mid;
}
return -1;
}
};
朴素二分模版：
while(left<=right)//每次查找的元素都是未知的，所以要取等号
{
int mid=left+(right-left)/2; //防止溢出，替换成left+（right-left+1)也可以，只不过是偶数个元素时，mid有2个中间值，左右均可
if(……)
right=mid-1;
else if(……)
left=mid+1;
else
return ……;
}
2.在排序数组中查找元素的第一个和最后一个位置
题目描述：
给你一个按照非递减顺序排列(趋势要么递增要么不变)的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：
nums = [5,7,7,8,8,10], target = 8
输出：[3,4]示例 2：
输入：
nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]示例 3：
输入：
nums = [], target = 0
输出：[-1,-1]提示：
- 0 <=
nums.length<= 105- -109 <=
nums[i]<= 109nums是一个非递减数组- -109 <=
target<= 109
解法一：暴力查找
从前往后枚举每一个元素，将其与目标值进行对比，相同时记为begin，继续向后寻找，直到找到该数的末尾位置记为end。返回begin,end即可。
时间复杂度最差为O(N)。
解法二：二分查找
当数组具有“二段性”时，我们就可以用二分查找算法。接下来我们来寻找该数组的“二段性”.
记左边界为Bleft，右边界为Bright.
1.查找区间的左端点
这里，我们把数组的元素分为两部分——小于target的部分[left,Bleft-1] and 大于等于target的部分[Bleft,right]。
- 当mid在[left,Bleft-1]的区间，要找左区间，我们可以直接舍去[left,mid]，更新left=mid+1;
- 当mid在[Bleft,right]的区间，要找左区间，我们可以直接舍去[mid+1,right]，更新right=mid(因为mid可能是最终结果)；
- 之后在[left,right]上继续寻找左边界。
细节处理：
1.循环条件：
left<right；
- left=right时，就是最终结果，无需判断；如果判断，就会死循环。
2.求中点的操作：
正确写法：left+(right-left)/2：求的是靠左的位置（向下调整）。
找左端点时求中点要向下取整。
要是向上调整，判断之后，当mid在[Bleft,right]时，要更新right=mid。再进行下一次判断，要是又面对同样的情况，又更新right=mid……又循环往复……
2.查找区间右端点：
这里，我们把数组的元素分为两部分——小于等于target的部分[left,Bright] and 大于target的部分[Bright+1,right]。
- 当mid在[left,Bright]的区间，要找右区间，我们可以直接舍去[left,mid-1]，更新left=mid(因为mid可能是最终结果);
- 当mid在[Bright+1,right]的区间，要找右区间，我们可以直接舍去[mid,right]，更新right=mid-1;
- 之后在[left,right]上继续寻找右边界。
细节处理：
1.循环条件：
left<right
2.求中点的操作：
正确写法：left+(right-left+1)/2：求的是靠右的位置（向上调整）;
找右端点时求中点要向上取整。
要是向下调整，判断之后，当mid落在[left,Bright]时，要更新left=mid。再进行下一次判断，要是又面对同样的情况，又要更新left=mid……又循环往复……
代码实现：
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
// 处理边界情况
if(nums.size() == 0)
return {-1, -1};
int begin = 0;
// 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)
return {-1, -1};
else
begin = left; // 标记⼀下左端点
// 2. 二分右端点
left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(nums[mid] <= target)
left = mid;
else
right = mid - 1;
}
return {begin, right};
}
};
查找区间左端点的模版：
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(……) left = mid;
else right = mid - 1;
}
总结切记：分类讨论的代码，就题论题即可。
3.搜索插入位置
题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
算法思路：
本题数组是一个排序数组，具有“二段性”时，我们就可以用二分查找算法。
- 设插入位置的坐标为x，根据插入位置的特点可以把数组的元素分为两部分——小于target的部分[left , x-1] and 大于等于target的部分[x , right]。
- 当mid在[left, x-1]的区间，我们可以直接舍去[left, mid]，更新left=mid+1;
- 当mid在[x, right]的区间，我们可以直接舍去[mid+1,right]，更新right=mid(因为mid可能是最终结果)；
- 之后在[left,right]上继续查找。
- 直到我们的查找区间的长度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果。
代码实现：
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 right + 1;
return right;
}
};
4.x 的平方根
题目描述：
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。示例 1：
输入：x = 4
输出：2示例 2：
输入：x = 8
输出：2解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
解法一：暴力查找
算法思路：
依次枚举 [0, x] 之间的所有数 i ：
-
如果 i * i == x ，直接返回 x ；
-
如果 i * i > x ，说明之前的⼀个数是结果，返回 i - 1 。
由于 i * i 可能超过 int 的最大值，因此使用 long long 类型。
代码实现：
class Solution {
public:
int mySqrt(int x) {
// 由于两个较⼤的数相乘可能会超过 int 最⼤范围
// 因此⽤ long long
long long i = 0;
for (i = 0; i <= x; i++)
{
// 如果两个数相乘正好等于 x，直接返回 i
if (i * i == x) return i;
// 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数
if (i * i > x) return i - 1;
}
// 为了处理oj题需要控制所有路径都有返回值
return -1;
}
};
解法二：二分查找
本题数组具有“二段性”时，我们就可以用二分查找算法。
算法思路：
这里，我们把数组的元素分为两部分——平方后小于等于x的部分[1,mid] and 平方后大于x的部分[mid-1, x]。
定义 left ， right 指针，分别指向数组的左右区间。
当left<right时，下列一直循环：
找到待查找区间的中间点 mid ，找到之后分三种情况讨论：
- mid*mid<=x：更新left=mid
- mid*mid>x：更新right=mid-1
代码实现：
class Solution
{
public:
int mySqrt(int x)
{
if(x < 1) return 0; // 处理边界情况
int left = 1, 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;
}
};
最后，本篇文章到此结束，感觉不错的友友们可以一键三连支持一下笔者，有任何问题欢迎在评论区留言哦~