我爱学算法之—— 二分查找（下）

一、寻找峰值

题目解析

对于这道题，给定一个数组nums，在这数组中，可能存在多个峰值元素，我们只需找到一个峰值，然后返回峰值索引即可。

峰值元素：严格大于左右相邻的元素。

题目中给定：nums[0]和nums[n]可以看做负无穷。

算法思路

对于这道题，首先暴力解法：遍历整个数组，依次判断一个元素它是不是峰值元素。

暴力解法的时间复杂度是O(n)；并且暴力解法它并没有用到题目中给的：nums[0]和nums[n]可以看做负无穷这一个条件。

当我们遍历i位置时，有且仅有两种情况：递增/递减（题目给定 nums[i] != nums[i+1]）。

当i位置呈现递增趋势时，也就是nums[i] > nums[i+1]，题目又给出nums[0] = nums[n] = -∞区间[left , i]：也就是左边区间内，因为最左侧是负无穷，所以左侧区间要么一直递增，要么既有递增也有递减（开始位置肯定是先递增在递减）如果一直递增，那i位置就是一个峰顶；如果既有递增也有递减，那左侧区间内一定存在峰顶。也就是说，左侧区间内一定存在峰顶区间[i+1 , right]：也就是右侧区间，因为最右侧是负无穷，所以右侧区间可能一直递减，也可能既有递增也有递减如果一直递减，那右侧区间就不存在峰顶（因为nums[i+1] < nums[i]）；如果既有递增也有递减，那右侧区间是存在峰顶的。那也就是说，右侧区间不一定存在峰顶

同理，如果i位置呈递减趋势，也就是nums[i] < nums[i+1]时：左侧区间不一定存在峰顶右侧区间一定存在峰顶

所以，遍历i位置时，就会把数组划分成区间[left , i]和区间[i+1 , right]；这两个区间一个是一定存在峰顶的，一个是不一定存在峰顶的。

所以我们就可以根据二段性，使用二分查找算法

定义left,right，取mid = left + (right - left)/2如果nums[mid] > nums[mid+1]：左侧区间一定存在峰顶，去左侧区间查找如果nums[mid] < nums[mid+1]：右侧区间一定存在峰顶，去右侧区间查找

代码实现

classSolution{public:intfindPeakElement(vector<int>& nums){int l =0, r = nums.size()-1;while(l < r){int mid = l +(r - l)/2;if(nums[mid]> nums[mid +1]) r = mid;else l = mid +1;}return l;}};

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

题目解析

对于这道题，给定一个数组，这个数组是由一个有序的数组经过1-n次旋转得来的；

每一次旋转，就是将数组的最后一个元素放到数组的开头。

题目中还告诉我们数组nums中的元素互不相同。

最后让我们找到数组nums中的最小值，然后返回。

算法思路

暴力解法：

遍历整个数组，找到数组中的最小值，然后返回。

题目中告诉我们，nums数组是由一个有序的数组经过旋转得来的；而每一次旋转都是将数组的最后一个元素放到数组的第一个位置。

那这样我们的数组nums中的数据，前一部分是递增的，后一部分也是递增的；并且前一部分的数据都是大于后一部分的数据的。（因为旋转前数据是有序的）

但是有一个特殊情况，数组nums也可以是有序的；也就是原数组旋转之后的数组nums和它自己是一样的。

所以数组nums就可以分为两部分，一部分是大于nums[n-1]的；另一部分是小于等于nums[n-1]的。

我们就可以利用该二段性，使用二叉查找算法

而我们要查找数组nums中的最小值，很显然我们要查找的最终结果在小于nums[n-1]的部分，且是该部分的最左端。

所以我们数组nums中的最小值就变成了，查找大于等于nums[n-1]区间的左端点。

定义left,right，取mid = left + (right - left)/2

如果nums[mid] > nums[n-1]：我们查找的最终结果位于区间[mid+1 , right]

如果nums[mid] <= nums[n-1]：我们查找的最终结果位于区间[left , mid]

特殊情况，如果数组nums是有序的，我们查找的是小于nums[n-1]的区间左端点，也是最终结果。

代码实现

classSolution{public:intfindMin(vector<int>& nums){int n = nums.size();int l =0, r = n -1;while(l < r){int mid = l +(r - l)/2;if(nums[mid]> nums[n -1]) l = mid +1;else r = mid;}return nums[l];}};

三、点名 - 力扣

题目解析

n名同学学号是0 ~ n-1，现在给定一个数组（点名结果记录）records，现在有一个同学缺席，现在我们要找到这个缺席的学生的学号。

例如：0,1,2,3,5，数组中不存在4；

算法思路

对于这道题，还是比较简单的，解法有有很多种：

hash表，使用hash表来记录每一个数字，最后遍历hash表找到没有出现的数字。暴力查找，遍历整个数组，依次查找找到第一个数据和下标不相等的元素。按位与运算：x&x = 0，0&x = x；所以遍历整个元素，依次按位与上元素和下标+1，这样最后结果就是缺失的数字。数学运算，求出1-n的和，然后依次减去每一个元素，最终结果就是缺失的数字。

当然，上述的解法的时间复杂度都是O(n)的；

我们知道数组中的数据是0~n，是缺失一个数字的；那这个缺失的数字把数组分成了两部分：

左侧区域：数组中的数据和下标是相等的；右侧区域：数组中的数据和下标是不相等的。

而我们要查找的是右侧区域的左端点的下标，因为这个下标就是缺失的数字；

所以，我们就可以利用该二段性使用二分查找

定义left,right，取mid如果records[mid] == mid：我们要查找的最终结果在区间[mid+1 , right]中 -> left = mid+1;如果records[mid] != mid：我们要查找的最终结果在区间[left , mid]中 -> right = mid;

这里有个特殊情况，就是数组缺失的是最后一个元素，此时是不存在records[i] != i的区间的；

进行特殊处理，如果records[n-1] == n-1，就返回records[n-1] + 1。

代码实现

classSolution{public:inttakeAttendance(vector<int>& records){if(records.back()== records.size()-1)return records.back()+1;int l =0, r = records.size()-1;while(l < r){int mid = l +(r - l)/2;if(records[mid]== mid) l = mid +1;else r = mid;}return l;}};

到这里本篇文章内容就结束了，感谢各位大佬的支持