【算法一周目】数据深处的舞者：二分查找的优雅与力量

文章目录

• 1.二分查找
• 2.在排序数组中查找元素的第一个和最后一个位置
• 3.搜索插入位置
• 4. x 的平方根
• 5.山峰数组的峰顶
• 6.寻找峰值
• 7.搜索旋转排序数组中的最小值
• 8.0～n-1 中缺失的数字

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 相等的数，返回下标。

classSolution{public:intsearch(vector<int>& nums,int target){for(int i =0; i < nums.size();++i){if(nums[i]== target)return i;}return-1;}};

但是这种方法时间复杂度是 O(log n) ，且没有利用到数组的有序性，略微不足。

方法二：二分查找

利用数组的有序性，先从数组的中间位置的数开始比较，根据比较结果将数组的查找范围缩小。

具体过程如下：

1. 初始化 left 和 right 指针分别指向数组的开头和末尾。
2. 计算中间位置 mid = left + (right - left) / 2。（ mid = (left + right) / 2 计算过程中结果可能会溢出，不采用。）
3. 比较中间元素与目标值：
   • 若 nums[mid] == target，返回 mid 。
   • 若 nums[mid] > target，根据有序性，mid 右边部分的数肯定比 target 大，舍去右边区间，target· 应该在数组的左半部分，更新 right = mid - 1；
   • 若 nums[mid] < target，mid 左边部分的数肯定比 target 小，舍去左边区间，target· 应该在数组的右半部分，更新 left = mid + 1。
4. 当 left > right 时，结束循环，target 不在数组内，返回 -1 。

classSolution{public:intsearch(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;elseif(target < nums[mid]) right = mid -1;elsereturn 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⁵。
• -10⁹ <= nums[i] <= 10⁹。
• nums 是一个非递减数组。
• -10⁹ <= target <= 10⁹。

解题思路

题目要求实现时间复杂度为 O(log n) 的算法去找到目标值在数组中的开始位置和结束位置，我们容易就想到了二分查找解决问题。

所以我们只需要利用两次二分查找找到目标值区间在数组中的左端点和右端点即可。

具体过程如下：

1. 查找左端点：

• 定义指针 left 和 right 分别指向数组的开头与末尾，计算数组中间位置 mid = left + (right - left) / 2 。
  • 若 nums[mid] < target ，说明目标值在右边，舍弃左边区间，更新 left = mid + 1 。
  • 若 nums[mid] >= target ，说明目标值在 mid 位置或者 mid 的左边，舍弃右边区间，更新 right = mid 。
• 当 left == right 时，结束循环。

2. 检查 nums[left] 是否与目标值相等，若不相等，说明目标值不在数组内，返回 {-1, -1} ；若相等，说明找到目标值区间的左端点，用变量 LeftPoint 记录左端点，继续查找其右端点。
3. 查找右端点：

• 定义指针 left 和 right 分别指向数组的开头与末尾，计算数组中间位置 mid = left + (right - left + 1) / 2 。
  • 若 nums[mid] > target ，说明目标值在左边，舍弃右边区间舍，更新 right = mid - 1 。
  • 若 nums[mid] <= target ，说明目标值在 mid 位置或者 mid 的右边，舍弃左边区间，更新 left == right 。
• 当 left == right 时，结束循环。

4. 返回结果 {LeftPoint, right} 。

细节问题：

1. 循环条件：left < right ，如果是取等号，会有死循环的风险。
   • 以查找左端点为例，当循环进行到 left == right 时，如果 nums[mid] < target 时，更新 left = mid + 1 ，可以结束循环，但是如果 nums[mid] >= target 时，更新 right = mid，left、right、mid 将会一直处于同一位置，程序就会一直循环；查找右区间也是同理。
2. 计算中间下标的不同，查找左区间：mid = left + (right - left) / 2 ，查找右区间：mid = left + (right - left + 1) / 2。
   • 这两种计算下标的方式只有在数组元素是偶数个时才会有所不同，前者得到的中间偏左的位置，后者得到的是中间偏右的位置。如果错误使用这两种计算中间下标的方式，程序也是可能会死循环的。还是以查找左端点为例，如果使用的查找右端点的方式，当 left 和 right 相邻时，计算得到的 mid 就会等于 right，如果 nums[mid] >= target ，更新 right = mid，程序就会陷入死循环。

代码实现

classSolution{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⁴
• 104 <= nums[i] <= 10⁴
• nums 为 无重复元素的升序排列数组
• 10⁴ <= target <= 10⁴

解题思路

根据题目要求，我们应该要使用二分查找算法来解决问题。

分析题目，我们得出题目要求的是查找大于等于 target 的区间的左端点，因为当 target 在数组中不存在时，第一个大于 target 的元素下标就是插入位置（示例2）。

具体过程：

1. 定义指针 left 和 right 分别指向数组的开头与末尾。
2. 计算数组中间位置 mid = left + (right - left + 1) / 2 。
   • 若 nums[mid] < target ，说明目标位置在右边，舍弃左边区间，更新 left = mid + 1 。
   • 若 nums[mid] >= target ，说明目标位置在 mid 位置或者 mid 的左边，舍弃右边区间，更新 right = mid 。
   • 当 left == right 时，结束循环。
3. 边界情况的处理：
   • 如果数组的元素全都小于 target 的（示例3），那么插入位置应该数组最后一个元素的下一个位置（下标为数组元素大小的位置）。
4. 返回结果 left 。

代码实现

classSolution{public:intsearchInsert(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³¹ - 1

解题思路

方法一：暴力查找

遍历 0 到 x 的平方根 i ，若 i * i == x，返回 i；若 i * i > x ，返回 i - 1 。

classSolution{public:intmySqrt(int x){// 由于两个较大的数相乘可能会超过 int 最大范围，因此用 long longlonglong i =0;for(i =0; i <= x; i++){// 如果两个数相乘正好等于 x，直接返回 iif(i * i == x)return i;// 如果第一次出现两个数相乘大于 x，说明结果是前一个数if(i * i > x)return i -1;}// 为了处理oj题需要控制所有路径都有返回值,防止编译报错return-1;}};

时间复杂度是 O(x^1/2)，不是最优解法。

方法二：二分查找
由于 0 到 x 的平方 i * i，是有序的，具有二段性，因此我们可以使用二分查找算法解决问题。

进一步分析题目，其实要查找的是 i 的平方小于等于 x 区间的右端点 。

具体过程：

1. 定义 left 指向 1，right 指向 x 。
2. 计算中间位置 mid = left + (right - left + 1) / 2 （查找右端点）。
   • 若 mid * mid <= x ，说明平方根在 mid 位置或者 mid 的右边，舍弃左边区间，更新 left = mid 。
   • 若 mid * mid > x ，说明平方根在 mid 的左边区间，舍弃右边区间，更新 right = mid - 1 。
3. 当 left == right 时，结束循环，返回结果 left 。

细节问题：mid 的类型应该是 long long ，因为两数相乘可能超过整型最大值。

classSolution{public:intmySqrt(int x){//对x为0的情况特殊处理if(x ==0)return0;//查找i的平方小于等于x区间的右端点int left =1, right = x;while(left < right){//防止两数相乘溢出longlong 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⁴
• 0 <= arr[i] <= 10⁶
• 题目保证 arr 是山脉数组。

解题思路

方法一：暴力查找

遍历数组的每一个元素，找到一个大于两边相邻元素的数，返回其下标即可。

classSolution{public:intpeakIndexInMountainArray(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;// 为了防止编译报错，所有路径必须有返回值}};

方法二：二分查找

由题目可以知道，一是山峰数组是没有重复元素的；二是山峰数组是具有二段性的，整个山峰数组只有上升趋势和下降趋势，所以我们可以使用二分查找算法来解决问题；
进一步分析题目，题目要求的峰顶索引其实就是上升趋势区间的右端点或者下降趋势区间的左端点。

这里以查找上升趋势区间的右端点为例。

具体解题过程：

1. 初始化 left 和 right 分别指向山峰数组的开头与末尾。
2. 计算山峰数组中间位置 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 时，结束循环。
3. 返回峰顶索引 left 。

classSolution{public:intpeakIndexInMountainArray(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;}};

classSolution{public:intpeakIndexInMountainArray(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³¹ <= nums[i] <= 2³¹ - 1
• 数组中的所有元素 nums[i] 均不同。

解题思路

这道题与 852. 山脉数组的峰顶索引 类似，我们可以利用二分算法来查找上升趋势区间的右端点或者下降趋势区间的左端点。

这里以查找下降趋势区间的左端点为例。

具体解题过程：

1. 初始化 left 和 right 分别指向数组的开头与末尾。
2. 计算数组中间位置 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 时，结束循环。
3. 返回峰值索引 left。

两种查找方式的代码实现：

classSolution{public:intfindPeakElement(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;}};

classSolution{public:intfindPeakElement(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.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• 数组中的所有整数互不相同
• 数组已按升序排列，并进行了旋转

解题思路

分析题目，我们不难得出旋转数组是具有二段性的，整个旋转数组可以根据数组的末尾元素 last 的比较划分出两个区间。

根据二段性，查找最小值其实就是找小于等于 last 元素区间的左端点，我们就可以得出具体二分算法的步骤：

1. 初始化 left 和 right 分别指向数组的开头与末尾。
2. 计算数组中间位置 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 。
3. 当 left == right 时，结束循环，返回最小值 left 。

其实这道题也是可以以数组的起始元素作为基准值来划分区间，由此推出与上述不同的另一种二分算法，但是该二分算法没有办法处理旋转数组完全升序或者完全降序的情况，而上述的二分算法是可以处理两种旋转数组的特殊情况的。

代码实现

classSolution{public:intfindMin(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 数组的元素放进哈希表，再遍历哈希表来查找缺失的元素。

classSolution{public:inttakeAttendance(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) 。

方法二：直接遍历

直接遍历数组，找到数组元素与其下标不相等的元素，其下标就是缺失的元素。

classSolution{public:inttakeAttendance(vector<int>& records){for(int index =0; index < records.size(); index++){if(records[index]!= index)return index;}//特殊处理缺失的元素有可能就是最后一个元素的情况return records.size();}};

方法三：异或

在不缺失任何一个数的情况，将 0 到 n - 1 全部异或，再将得到的数与 records 的元素异或，根据异或的性质就可以得到缺失的数。

classSolution{public:inttakeAttendance(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 的和，然后将去缺失元素数组的元素，最后得到缺失的值。

classSolution{public:inttakeAttendance(vector<int>& records){int LastElement = records.size();//等差数列求和int sum = LastElement *(LastElement +1)/2;for(auto e : records) sum -= e;return sum;}};

方法五：二分查找

分析题目，给定缺失元素的数组是具有二段性的，可以根据数组元素与其下标是否相等划分出两个区间：数组元素与其下标相等的区间和数组元素与其下标不相等的区间，题目要求的**缺失的数其实就是数组元素与其下标不相等的区间的左端点**，我们就可以用二分查找来解决问题。

具体解题过程：

1. 初始化 left 和 right 分别指向数组的开头与末尾。
2. 计算数组中间位置 mid = left + (right - left ) / 2 。
   • 若 nums[mid] == mid，说明 mid 处于相等区间，缺失值在 mid 右边，舍弃左边区间，更新 left = mid + 1 。
   • 若 nums[mid] != mid，说明 mid 处于不相等区间，缺失值在 mid 位置或者 mid 左边，舍弃右边区间，更新 right = mid 。
3. 当 left == right 时，结束循环。
4. 特殊情况的处理，当缺失了最后一个数字时，整个数组的元素都与其下标相等，结束循环 left 指向数组的最后一个位置，此时要返回（缺失的元素） left + 1，其他情况返回 left 即可。

classSolution{public:inttakeAttendance(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)

Have a good day😏

See you next time, guys!😁✨🎞