【二分查找】--- 进阶题目赏析

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:         9ilk

(๑•́ ₃ •̀๑) 文章专栏：      算法Journey

---

本篇博客我们继续来了解一些有关二分查找算法的进阶题目。

---

🏠 寻找峰值

📌 题目内容

162. 寻找峰值 - 力扣（LeetCode）

📌 题目解析

• 与山脉数组那道题不同的是，本题数组内存在多个峰值。
• 注意本题一个规定，即num[-1] = num[n] = 负无穷，数组边界都是最小负无穷。

📌算法原理

📒  思路一：暴力解法

有三种情况下，某个数是峰值，我们暴力解法只需要遍历一遍数组进行分类情况即可，但是时间复杂度是O(N)不符合题意。

📒 思路二：二分查找

我们发现：

1. 当arr[i] > arr[i+1]时，此时左边区域一定存在峰值，因此我们要向左缩小范围。

2.当arr[i] <  arr[i+1]时，此时右边区域一定存在峰值，因此我们要向右缩小范围。

3.由于峰值位置的不确定我们需要寻找峰值，因此在寻找峰值的过程中，我们发现了二段性因此可以使用二分查找。

二分过程：

1. arr[i] > arr[i+1]  --->  right = mid , 此时mid处可能就是峰值所以不能跳过mid。

2. arr[i] < arr[i+1]  --->  left   = mid +1 ,此时mid+1处才可能是峰值，因此可以跳过mid。

参考代码：

class Solution 
{public:int findPeakElement(vector<int>& nums) {int left  = 0;int right = nums.size()-1;while(left < right){int mid = left + (right - left ) / 2;if( nums[mid] <  nums[mid+1]){left = mid + 1 ;}elseright = mid;}return left;}};

---

🏠 寻找旋转排序数组中的最小值

📌 题目内容

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

📌 题目内容

• 注意题目数组中的数字各不相同。

📌算法原理

📒 思路一：暴力解法

暴力解法思路很简单，可以定义一个min变量，遍历一遍数组，遇到比他小的就更新min,时间复杂度是O(N),并不符合题目要求。

📒 思路二：二分查找

题目要我们找旋转排序数组中的最小值，这个位置是“确定”的，整个数组的大小变化趋势如上图。以D为参考点，我们发现：

1.  最小值所在位置的左边，都是严格大于等于数组最后一个数的。

2.最小值所在位置的右边，都是小于等于数组最后一个数的。

3.本题要我们求的很明显地划分了两段区间，体现了二段性，我们要做的是思考如果mid落在划分的两段区间内，我们如何靠近目标。

二分流程：

1. 当nums[mid] > nums[n-1]时，说明mid处于AB段，此时我们需要向右缩小范围，left = mid+1.

2.当nums[mid] <= nums[n-1]时，说明mid位于CD段，此时我们需要向左缩小范围，由于目标在CD段上，因此更新right时我们不能跳过mid因为mid可能就是最小值。

参考代码：

class Solution {
public:int findMin(vector<int>& nums) {int  left = 0;int right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < nums[right])right = mid;else left = mid+1;}return nums[left];  }};

思考：我们划分两端区间是以D为参考点，那么我们是否能以A为参考点呢？

1. A~B段是大于等于nums[0](A点)的，而C~D段是严格小于nums[0]的。

2.此时二分流程：

A - B : nums[i]>=nums[0] --> left= mid +1;
C - D : nums[i] < nums[0] --> right = mid;
3.当旋转数组旋转到原来升序时：

此时A点就是最小值，区间不断向右，此时就会丢掉最小值，因此对于这种边界情况我们需要特殊处理。

class Solution {
public:int findMin(vector<int>& nums) {int  left = 0;int right = nums.size() - 1;if(nums[0] < nums[right])return nums[0];int x = nums[0]; //以A为参照while(left < right){int mid = left + (right - left) / 2;if(nums[mid] >= x )left = mid + 1;else right = mid;}return nums[left];  }};

🏠 0~n-1中缺失的数字

📌 题目内容

LCR 173. 点名 - 力扣（LeetCode）

📌 题目内容

• 注意：对于[0,1,2,3,4]这样的数组，此时缺失的数字应该为5.

📌算法原理

📒 思路一：哈希表

由于缺了一个数字，因此总的人数为数组元素个数+1，此时我们先遍历一遍数组进行映射，再从0-N遍历，没有映射的就是缺失的数字。

class Solution {
public:int takeAttendance(vector<int>& records) {unordered_map<int,int> mp;for(const auto& e : records){mp[e]++;}int reasult = 0;int n = records.size() + 1; for(int i = 0 ; i < n ; i ++){if(mp[i] == 0){reasult = i;break;}}return reasult;}
};

📒 思路二：直接遍历找结果

由于学号从0开始，因此数组中每个数都应该与下标相同，由于缺失了一个数，可能导致它的下一个数占它的位置，也可能他就是最后一个数。

class Solution {
public:int takeAttendance(vector<int>& records) {bool flag = false;int i = 0;for( i = 0 ; i < records.size();i++){if(i != records[i]){flag = true;break;}}return i;}
};

📒 思路三：位运算

既然知道应到同学的人数n，又根据按位异或a^a = 0 的性质，我们可以用ret遍历一遍数组进行异或，再从0-N异或，最后ret就是缺失的数字。

class Solution {
public:int takeAttendance(vector<int>& records) {int n =  records.size();int sum = 0;for(int i = 0 ;i <= n ;i++){sum ^= i;}for(int i = 0; i < records.size();i++){sum ^= records[i];}return sum;}
};

📒 思路四：高斯求和公式

由于我们知道了应到学生人数，因此我们可以用等差数列求原本应该的学号之和，再遍历数组减去，最后得到的就是缺失的数字。

class Solution {
public:int takeAttendance(vector<int>& records) {int n =  records.size() + 1;int sum = 0 + (n*(n-1)) / 2;cout << sum <<endl;for(int i = 0; i < records.size();i++){sum -= records[i];}return sum;}
}；

📒 思路五：二分查找

前面的思路都很简单，但时间复杂度都是O(N)。仔细观察我们发现因为缺失了数字，会造成二段性。

我们发现，由于缺失了一个数字造成了二段性：

1. 左边一段区间的值都与下标相同，而右边一段区间的值与下标不匹配，因此我们需要去靠近第一个不与下标匹配的值。此时这个值的下标就是缺失的数字。

2.nums[mid] = mid时，说明mid在左边，此时需要向右缩小范围。

3.nums[mid] ≠ mid时，说明mid在右边，此时mid可能就是我们要找的，因此不能跳过mid.

4.需要注意的是对于类似[0,1,2,3,4]这样的情况，最后left==right时，我们需要返回left+1.

参考代码：

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0;int right = records.size() - 1;while(left < right){int mid = left + (right - left ) / 2;if(records[mid] == mid)left = mid + 1;elseright = mid;       }if(records[left] != left) return left;return left + 1; }
};

---

总结：

1. 当题目很明确要求的目标能划分二段性时，我们需要考虑的是在划分区间内怎么接近目标。

2.当不是很明确二段性时，我们要考虑的是在找目标的过程中能否发现二段性。