1. 二分查找
题目链接：704. 二分查找
题目描述：
给定一个升序排列的整数数组 nums，和一个目标值 target。如果 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的长度范围为[1, 10000]。 - 数组
nums的每个元素都在[-9999, 9999]之间。
解题思路
方法一：暴力遍历
从前往后遍历数组，遇到与 target 相等的数，返回下标。
class Solution {
public:
int search(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == target) return i;
}
return -1;
}
};
但是这种方法时间复杂度是 O(n) ，且没有利用到数组的有序性，略不足。
方法二：二分查找
利用数组的有序性，先从数组的中间位置的数开始比较，根据比较结果将数组的查找范围缩小。
具体过程如下：
- 初始化
left和right指针分别指向数组的开头和末尾。 - 计算中间位置
mid = left + (right - left) / 2。（mid = (left + right) / 2计算过程中结果可能会溢出，不采用。） - 比较中间元素与目标值：
- 若
nums[mid] == target，返回mid。 - 若
nums[mid] > target，根据有序性，mid右边部分的数肯定比target大，舍去右边区间，target应该在数组的左半部分，更新right = mid - 1； - 若
nums[mid] < target，mid左边部分的数肯定比target小，舍去左边区间，target应该在数组的右半部分，更新left = mid + 1。
- 若
- 当
left > right时，结束循环，target不在数组内，返回-1。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
// 当 left == right 时还需要比较
while (left <= right) {
// 计算中间值的下标，注意防溢出
int mid = (right - left) / 2 + left;
if (target > nums[mid]) left = mid + 1;
else if (target < nums[mid]) right = mid - 1;
else return mid;
}
return -1;
}
};
- 时间复杂度：每次比较都会将查找范围缩小一半，时间复杂度为
O(log n)。 - 空间复杂度：
O(1)
2. 在排序数组中查找元素的第一个和最后一个位置
题目链接：34. 在排序数组中查找元素的第一个和最后一个位置
题目描述：
给定一个按非递减顺序排列的整数数组 nums，和一个目标值 target，请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
- 输入：
nums = [5,7,7,8,8,10], target = 8 - 输出：
[3, 4] - 解释：目标值
8在数组中的起始位置为下标3，结束位置为下标4。
示例 2：
- 输入：
nums = [5,7,7,8,8,10], target = 6 - 输出：
[-1, -1] - 解释：目标值
6不存在于数组中，因此返回[-1, -1]。
示例 3：
- 输入：
nums = [], target = 0 - 输出：
[-1, -1] - 解释：空数组中没有任何目标值，因此返回
[-1, -1]。
提示：
- 0 <=
nums.length<= 10^5。 - -10^9 <=
nums[i]<= 10^9。 nums是一个非递减数组。- -10^9 <=
target<= 10^9。
解题思路
题目要求实现时间复杂度为 O(log n) 的算法去找到目标值在数组中的开始位置和结束位置，我们容易就想到了二分查找解决问题。
所以我们只需要利用两次二分查找找到目标值区间在数组中的左端点和右端点即可。
具体过程如下：
- 查找左端点：
- 定义指针 left 和 right 分别指向数组的开头与末尾，计算数组中间位置
mid = left + (right - left) / 2。- 若
nums[mid] < target，说明目标值在右边，舍弃左边区间，更新left = mid + 1。 - 若
nums[mid] >= target，说明目标值在mid位置或者mid的左边，舍弃右边区间，更新right = mid。
- 若
- 当
left == right时，结束循环。
- 检查
nums[left]是否与目标值相等，若不相等，说明目标值不在数组内，返回{-1, -1}；若相等，说明找到目标值区间的左端点，用变量LeftPoint记录左端点，继续查找其右端点。 - 查找右端点：
- 定义指针
left和right分别指向数组的开头与末尾，计算数组中间位置mid = left + (right - left + 1) / 2。- 若
nums[mid] > target，说明目标值在左边，舍弃右边区间，更新right = mid - 1。 - 若
nums[mid] <= target，说明目标值在mid位置或者mid的右边，舍弃左边区间，更新left = mid。
- 若
- 当
left == right时，结束循环。
- 返回结果
{LeftPoint, right}。
细节问题：
- 循环条件：
left < right，如果是取等号，会有死循环的风险。- 以查找左端点为例，当循环进行到
left == right时，如果nums[mid] < target时，更新left = mid + 1，可以结束循环，但是如果nums[mid] >= target时，更新right = mid，left、right、mid将会一直处于同一位置，程序就会一直循环；查找右区间也是同理。
- 以查找左端点为例，当循环进行到
- 计算中间下标的不同，查找左区间：
mid = left + (right - left) / 2，查找右区间：mid = left + (right - left + 1) / 2。- 这两种计算下标的方式只有在数组元素是偶数个时才会有所不同，前者得到的中间偏左的位置，后者得到的是中间偏右的位置。如果错误使用这两种计算中间下标的方式，程序也是可能会死循环的。还是以查找左端点为例，如果使用的查找右端点的方式，当
left和right相邻时，计算得到的mid就会等于right，如果nums[mid] >= target，更新right = mid，程序就会陷入死循环。
- 这两种计算下标的方式只有在数组元素是偶数个时才会有所不同，前者得到的中间偏左的位置，后者得到的是中间偏右的位置。如果错误使用这两种计算中间下标的方式，程序也是可能会死循环的。还是以查找左端点为例，如果使用的查找右端点的方式，当
代码实现
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0) return {-1, -1};
int left = 0, right = nums.size() - 1;
int mid = 0;
// 1. 查找左端点
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
// 2. 判断目标值是否在数组
int Leftpoint = 0; // 用于记录左端点
if (nums[left] != target) return {-1, -1};
else Leftpoint = left;
// 3. 查找右端点
// 程序走到这说明找到了目标值左端点，只需要更新 right 即可开始新一轮的查找
right = nums.size() - 1;
while (left < right) {
mid = left + (right - left + 1) / 2;
if (nums[mid] > target) right = mid - 1;
else left = mid;
}
return {Leftpoint, right};
}
};
- 时间复杂度：
O(log n) - 空间复杂度：
O(1)
3. 搜索插入位置
题目链接：35. 搜索插入位置
题目描述：
给定一个排序数组 nums 和一个目标值 target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你必须设计并实现时间复杂度为 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
提示:
- 1 <=
nums.length<= 10^4 - 10^4 <=
nums[i]<= 10^4 - nums 为 无重复元素的升序排列数组
- 10^4 <= target <= 10^4
解题思路
根据题目要求，我们应该要使用二分查找算法来解决问题。
分析题目，我们得出题目要求的是查找大于等于 target 的区间的左端点，因为当 target 在数组中不存在时，第一个大于 target 的元素下标就是插入位置（示例 2）。
具体过程：
- 定义指针
left和right分别指向数组的开头与末尾。 - 计算数组中间位置
mid = left + (right - left) / 2。- 若
nums[mid] < target，说明目标位置在右边，舍弃左边区间，更新left = mid + 1。 - 若
nums[mid] >= target，说明目标位置在mid位置或者mid的左边，舍弃右边区间，更新right = mid。 - 当
left == right时，结束循环。
- 若
- 边界情况的处理：
- 如果数组的元素全都小于
target的（示例 3），那么插入位置应该数组最后一个元素的下一个位置（下标为数组元素大小的位置）。
- 如果数组的元素全都小于
- 返回结果
left。
代码实现
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// 查找大于等于 target 区间的左端点
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) right = mid;
else left = mid + 1;
}
// 边界情况的处理，当数组的元素全部小于 target 时
// 结束循环时，left == n - 1（n 为数组元素的大小）
if (nums[left] < target) return left + 1;
return left;
}
};
- 时间复杂度：
O(log n) - 空间复杂度：
O(1)
4. x 的平方根
题目链接：69. x 的平方根
题目描述：
给定一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1：
- 输入：
x = 4 - 输出：
2
示例 2：
- 输入：
x = 8 - 输出：
2 - 解释：
8的算术平方根是2.82842...，由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
解题思路
方法一：暴力查找
遍历 0 到 x 的平方根 i，若 i * i == x，返回 i；若 i * i > x，返回 i - 1。
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;
}
};
时间复杂度是 O(sqrt(x))，不是最优解法。
方法二：二分查找
由于 0 到 x 的平方 i * i，是有序的，具有二段性，因此我们可以使用二分查找算法解决问题。
进一步分析题目，其实要查找的是 i 的平方小于等于 x 区间的右端点。
具体过程：
- 定义
left指向1，right指向x。 - 计算中间位置
mid = left + (right - left + 1) / 2（查找右端点）。- 若
mid * mid <= x，说明平方根在mid位置或者mid的右边，舍弃左边区间，更新left = mid。 - 若
mid * mid > x，说明平方根在mid的左边区间，舍弃右边区间，更新right = mid - 1。
- 若
- 当
left == right时，结束循环，返回结果left。
细节问题：mid 的类型应该是 long long，因为两数相乘可能超过整型最大值。
class Solution {
public:
int mySqrt(int x) {
// 对 x 为 0 的情况特殊处理
if (x == 0) return 0;
// 查找 i 的平方小于等于 x 区间的右端点
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;
}
};
- 时间复杂度：
O(log n) - 空间复杂度：
O(1)
5. 山峰数组的峰顶
题目链接：852. 山脉数组的峰顶索引
题目描述：
符合下列属性的数组 arr 称为山脉数组：
arr.length >= 3- 存在索引
i（0 < i < arr.length - 1），使得：arr[0] < arr[1] < ... < arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给定一个由整数组成的山脉数组 arr，返回其峰顶索引 i，即满足条件 arr[i] 是整个数组中最大的元素，并且左右两边的数据呈现先升后降的趋势。
示例 1：
- 输入：
arr = [0,1,0] - 输出：
1
示例 2：
- 输入：
arr = [0,2,1,0] - 输出：
1
示例 3：
- 输入：
arr = [24,69,100,99,79,78,67,36,26,19] - 输出：
2
提示：
- 3 <=
arr.length<= 10^4 - 0 <=
arr[i]<= 10^6 - 题目保证
arr是山脉数组。
解题思路
方法一：暴力查找
遍历数组的每一个元素，找到一个大于两边相邻元素的数，返回其下标即可。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n - 1; i++) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
return i; // 找到峰顶，返回索引
}
}
return -1; // 为了防止编译报错，所有路径必须有返回值
}
};
方法二：二分查找
由题目可以知道，一是山峰数组是没有重复元素的；二是山峰数组是具有二段性的，整个山峰数组只有上升趋势和下降趋势，所以我们可以使用二分查找算法来解决问题；
进一步分析题目，题目要求的峰顶索引其实就是上升趋势区间的右端点或者下降趋势区间的左端点。
这里以查找上升趋势区间的右端点为例。
具体解题过程：
- 初始化
left和right分别指向山峰数组的开头与末尾。 - 计算山峰数组中间位置
mid = left + (right - left + 1) / 2。- 若
arr[mid] > arr[mid - 1]，说明mid处于上升趋势，峰顶元素在mid位置或者mid的右边，舍弃左边区间，更新left = mid。 - 若
arr[mid] < arr[mid - 1]，说明mid处于下降趋势，峰顶元素在mid的左边，舍弃右边区间，更新right = mid - 1。 - 当
left == right时，结束循环。
- 若
- 返回峰顶索引
left。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
// 因为峰顶元素不会在开头和结尾，所以从 1 和 n-2 开始查找
int left = 1, right = arr.size() - 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;
}
};
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1, right = arr.size() - 2;
// 查找下降趋势区间的左端点的写法
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > arr[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
};
- 时间复杂度：
O(log n) - 空间复杂度：
O(1)
6. 寻找峰值
题目链接：162. 寻找峰值
题目描述：
峰值元素是指其值严格大于左右相邻元素的元素。给定一个整数数组 nums，找到任意一个峰值元素并返回其索引。你可以假设 nums[-1] = -∞ 和 nums[n] = -∞，即数组两端可以视为负无穷。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
- 输入：
nums = [1,2,3,1] - 输出：
2 - 解释：
3是峰值元素，返回其索引2。
示例 2：
- 输入：
nums = [1,2,1,3,5,6,4] - 输出：
1 或 5 - 解释：函数可以返回索引
1（峰值元素为2），或返回索引5（峰值元素为6）。
提示：
- 1 <= nums.length <= 1000
- -2^31 <=
nums[i]<= 2^31 - 1 - 数组中的所有元素
nums[i]均不同。
解题思路
这道题与 852. 山脉数组的峰顶索引 类似，我们可以利用二分算法来查找上升趋势区间的右端点或者下降趋势区间的左端点。
这里以查找下降趋势区间的左端点为例。
具体解题过程：
- 初始化
left和right分别指向数组的开头与末尾。 - 计算数组中间位置
mid = left + (right - left ) / 2。- 若
nums[mid] > nums[mid + 1]，说明在下降趋势，峰值一定存在于mid位置或者mid左侧，mid右侧可能存在峰值，因此舍弃右边区间，更新right = mid。 - 若
nums[mid] < nums[mid + 1]，说明在上升降趋势，峰值一定存在于mid右侧，舍弃左边区间，更新left = mid + 1。 - 当
left == right时，结束循环。
- 若
- 返回峰值索引
left。
两种查找方式的代码实现：
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
// 查找下降趋势区间的左端点
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
};
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]) left = mid;
else right = mid - 1;
}
return left;
}
};
- 时间复杂度：
O(log n) - 空间复杂度：
O(1)
7. 搜索旋转排序数组中的最小值
题目链接：153. 寻找旋转排序数组中的最小值
题目描述：
给定一个按升序排列的整数数组 nums，数组中的值互不相同。数组在传递给函数之前，在某个未知的下标 k（0 <= k < nums.length）上进行了旋转，使得数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 的形式。
请找出旋转后数组中的最小值。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
- 输入：
nums = [4,5,6,7,0,1,2] - 输出：
0
示例 2：
- 输入：
nums = [3,4,5,1,2] - 输出：
1
示例 3：
- 输入：
nums = [11,13,15,17] - 输出：
11
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000- 数组中的所有整数互不相同
- 数组已按升序排列，并进行了旋转
解题思路
分析题目，我们不难得出旋转数组是具有二段性的，整个旋转数组可以根据数组的末尾元素 last 的比较划分出两个区间。
根据二段性，查找最小值其实就是找小于等于 last 元素区间的左端点，我们就可以得出具体二分算法的步骤：
- 初始化
left和right分别指向数组的开头与末尾。 - 计算数组中间位置
mid = left + (right - left ) / 2。- 若
nums[mid] > last，说明mid处于大于last的区间，最小值在mid的右边，舍弃mid左边区间，更新left = mid + 1。 - 若
nums[mid] <= last，说明mid处于小于等于last的区间，最小值在mid位置或者mid的左边，舍弃mid右边区间，更新right = mid。
- 若
- 当
left == right时，结束循环，返回最小值left。
其实这道题也是可以以数组的起始元素作为基准值来划分区间，由此推出与上述不同的另一种二分算法，但是该二分算法没有办法处理旋转数组完全升序或者完全降序的情况，而上述的二分算法是可以处理两种旋转数组的特殊情况的。
代码实现
class Solution {
public:
int findMin(vector<int>& nums) {
// 选定最后一个值为基准值
int left = 0, right = nums.size() - 1;
int last = nums[right]; // 基准值
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > last) left = mid + 1;
else right = mid;
}
return nums[left];
}
};
- 时间复杂度：
O(log n) - 空间复杂度：
O(1)
8. 0～n-1 中缺失的数字
题目链接：剑指 Offer 53 - II. 0～n-1 中缺失的数字
题目描述：
一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1：
- 输入：
[0,1,3] - 输出：
2
示例 2：
- 输入：
[0,1,2,3,4,5,6,7,9] - 输出：
8
提示：
1 <= 数组长度 <= 10000
解题思路
方法一：哈希表
注意到 records 数组的大小是 10000，因为缺失了一个数字，所以我们直接开一大小为 10001 的数组作为哈希表，将 record 数组的元素放进哈希表，再遍历哈希表来查找缺失的元素。
class Solution {
public:
int takeAttendance(vector<int>& records) {
// 最后一个同学的学号
int n = records.size();
// 哈希表
int hash[10001] = {0};
for (auto e : records) hash[e]++;
// 遍历哈希表查找缺失的元素
for (int i = 0; i <= n; ++i) {
if (hash[i] == 0) return i;
}
// 保证所有路径都有返回值
return -1;
}
};
这种方法的时间复杂度和空间复杂度都是 O(n)。
方法二：直接遍历
直接遍历数组，找到数组元素与其下标不相等的元素，其下标就是缺失的元素。
class Solution {
public:
int takeAttendance(vector<int>& records) {
for (int index = 0; index < records.size(); index++) {
if (records[index] != index) return index;
}
// 特殊处理缺失的元素有可能就是最后一个元素的情况
return records.size();
}
};
方法三：异或
在不缺失任何一个数的情况，将 0 到 n - 1 全部异或，再将得到的数与 records 的元素异或，根据异或的性质就可以得到缺失的数。
class Solution {
public:
int takeAttendance(vector<int>& records) {
// 不缺失的情况下最后一个元素
int LastElement = records.size();
int target = 0;
for (int i = 0; i <= LastElement; ++i) target ^= i;
for (auto e : records) target ^= e;
return target;
}
};
方法四：等差数列求和
在不缺失数的情况下，计算 0 到 n - 1 的和，然后将去缺失元素数组的元素，最后得到缺失的值。
class Solution {
public:
int takeAttendance(vector<int>& records) {
int LastElement = records.size();
// 等差数列求和
int sum = LastElement * (LastElement + 1) / 2;
for (auto e : records) sum -= e;
return sum;
}
};
方法五：二分查找
分析题目，给定缺失元素的数组是具有二段性的，可以根据数组元素与其下标是否相等划分出两个区间：数组元素与其下标相等的区间和数组元素与其下标不相等的区间，题目要求的缺失的数其实就是数组元素与其下标不相等的区间的左端点，我们就可以用二分查找来解决问题。
具体解题过程：
- 初始化
left和right分别指向数组的开头与末尾。 - 计算数组中间位置
mid = left + (right - left ) / 2。- 若
nums[mid] == mid，说明mid处于相等区间，缺失值在mid右边，舍弃左边区间，更新left = mid + 1。 - 若
nums[mid] != mid，说明mid处于不相等区间，缺失值在mid位置或者mid左边，舍弃右边区间，更新right = mid。
- 若
- 当
left == right时，结束循环。 - 特殊情况的处理，当缺失了最后一个数字时，整个数组的元素都与其下标相等，结束循环
left指向数组的最后一个位置，此时要返回（缺失的元素）left + 1，其他情况返回left即可。
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;
}
// 特殊处理缺失最后一个数的情况
return records[left] == left ? left + 1 : left;
}
};
- 时间复杂度：
O(log n) - 空间复杂度：
O(1)
