目录
1.题目链接:34. 在排序数组中查找元素的第一个和最后一个位置
一、二分查找
1.题目链接:704. 二分查找
2.题目描述:
给定一个
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]
之间。
3.算法流程:
a. 定义 left , right 指针,分别指向数组的左右区间。
b. 找到待查找区间的中间点 mid ,找到之后分三种情况讨论:
- arr[mid] == target 说明正好找到,返回 mid 的值;
- arr[mid] > target 说明 [mid, right] 这段区间都是大于 target 的,因此舍去右边区间,在左边 [left, mid -1] 的区间继续查找,即让 right = mid - 1 ,然后重复 2 过程;
- arr[mid] < target 说明 [left, mid] 这段区间的值都是小于 target 的,因此舍去左边区间,在右边 [mid + 1, right] 区间继续查找,即让 left = mid + 1 ,然后重复 2 过程;
c. 当 left 与 right 错开时,说明整个区间都没有这个数,返回 -1
4.算法代码:
class Solution
{
public:
int search(vector<int>& nums, int target)
{
// 初始化 left 与 right 指针
int left = 0, right = nums.size() - 1;
// 由于两个指针相交时,当前元素还未判断,因此需要取等号
while (left <= right)
{
// 先找到区间的中间元素
int mid = left + (right - left) / 2;
// 分三种情况讨论
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
// 如果程序⾛到这⾥,说明没有找到⽬标值,返回 -1
return -1;
}
};
二、在排序数组中查找元素的第一个和最后一个位置
1.题目链接:34. 在排序数组中查找元素的第一个和最后一个位置
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]
3.算法流程:
用的还是二分思想,就是根据数据的性质,在某种判断条件下将区间一分为二,然后舍去其中一个区间,然后在另一个区间内查找;为了方便叙述,我们用 x 表示该元素, resLeft 表示左边界, resRight 表示右边界。
寻找左边界思路:
🌵寻找左边界:
我们注意到以左边界划分的两个区间的特点为:
- 左边区间 [left, resLeft - 1] 都是小于 x 的;
- 右边区间(包括左边界) [resLeft, right] 都是大于等于 x 的;
🌵因此,关于 mid 的落点,我们可以分为下面两种情况:
- 当我们的 mid 落在 [left, resLeft - 1] 区间的时候,也就是 arr[mid] <target 。说明 [left, mid] 都是可以舍去的,此时更新 left 到 mid + 1 的位置,继续在 [mid + 1, right] 上寻找左边界;
- 当 mid 落在 [resLeft, right] 的区间的时候,也就是 arr[mid] >= target 。说明 [mid + 1, right] (因为 mid 可能是最终结果,不能舍去)是可以舍去的,此时更新 right 到 mid 的位置,继续在 [left, mid] 上寻找左边界;
🌵由此,就可以通过二分,来快速寻找左边界;
注意:这里找中间元素需要向下取整。因为后续移动左右指针的时候:
- 左指针: left = mid + 1 ,是会向后移动的,因此区间是会缩小的;
- 右指针: right = mid ,可能会原地踏步(比如:如果向上取整的话,如果剩下 1,2 两个元素, left == 1 , right == 2 , mid == 2 。更新区间之后, left,right,mid 的值没有改变,就会陷入死循环)。
因此⼀定要注意,当 right = mid 的时候,要向下取整。
寻找右边界思路:
🌴寻找右边界:
用 resRight 表示右边界;我们注意到右边界的特点为:
- 左边区间 (包括右边界) [left, resRight] 都是小于等于 x 的;
- 右边区间 [resRight+ 1, right] 都是大于 x 的;
🌴因此,关于 mid 的落点,我们可以分为下面两种情况:
- 当我们的 mid 落在 [left, resRight] 区间的时候,说明 [left, mid - 1]( mid 不可以舍去,因为有可能是最终结果) 都是可以舍去的,此时更新 left 到 mid的位置;
- 当 mid 落在 [resRight+ 1, right] 的区间的时候,说明 [mid, right] 内的元素是可以舍去的,此时更新 right 到 mid - 1 的位置;
🌴由此,就可以通过二分,来快速寻找右边界;
注意:这里找中间元素需要向上取整。因为后续移动左右指针的时候:
- 左指针: left = mid ,可能会原地踏步(比如:如果向下取整的话,如果剩下 1,2 两个元素, left == 1, right == 2,mid == 1 。更新区间之后, left,right,mid 的值没有改变,就会陷入死循环)。
- 右指针: right = mid - 1 ,是会向前移动的,因此区间是会缩小的;
因此一定要注意,当 right = mid 的时候,要向下取整。
4.算法代码:
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
// 处理边界情况
if(nums.size() == 0)
return {-1, -1};
int begin = 0;
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;// 标记左端点
// 查找区间右端点
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};
}
};
三、x的平方根
1.题目链接:69. x 的平方根
2.题目描述:
给你一个非负整数
x
,计算并返回x
的 算术平方根 。由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如
pow(x, 0.5)
或者x ** 0.5
。示例 1:
输入:x = 4 输出:2示例 2:
输入:x = 8 输出:2 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
3.解法一(暴力解法)
🌴算法思路:
依次枚举 [0, x] 之间的所有数 i :(这里没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回了,往后的情况就不会再判断。反而研究枚举区间,既耽误时间,又可能出错)
- 如果 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;
}
};
4.解法二(二分查找算法)
🌴算法思路:
设 x 的平方根的最终结果为 index :
分析 index 左右两侧数据的特点:
- [0, index] 之间的元素,平方之后都是小于等于 x 的;
- [index + 1, x] 之间的元素,平方之后都是大于 x 的。
- 因此可以使用二分查找算法。
🌴算法代码:
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 right;
}
};
四、搜索插入位置
1.题目链接:35. 搜索插入位置
2.题目描述:
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
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
3.解法(二分查找算法)
🌴算法思路:
a. 分析插入位置左右两侧区间上元素的特点:
设插入位置的坐标为 index ,根据插入位置的特点可以知道:
- [left, index - 1] 内的所有元素均是小于 target 的;
- [index, right] 内的所有元素均是大于等于 target 的。
b. 设 left 为本轮查询的左边界, right 为本轮查询的右边界。根据 mid 位置元素的信息,分析下⼀轮查询的区间:
- 当 nums[mid] >= target 时,说明 mid 落在了 [index, right] 区间上,mid 左边包括 mid 本身,可能是最终结果,所以我们接下来查找的区间在 [left,mid] 上。因此,更新 right 到 mid 位置,继续查找。
- 当 nums[mid] < target 时,说明 mid 落在了 [left, index - 1] 区间上,mid 右边但不包括 mid 本身,可能是最终结果,所以我们接下来查找的区间在 [mid + 1, right] 上。因此,更新 left 到 mid + 1 的位置,继续查找。
c. 直到我们的查找区间的长度变为 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 left + 1;
return left;
}
};
五、二分模板
在求 mid 的时候,只有 right - 1 的情况下,才会向上取整(也就是 +1 取中间数)。