一、寻找峰值
题目解析
对于这道题，给定一个数组
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]：右侧区间一定存在峰顶，去右侧区间查找
代码实现
class Solution {
public:
int findPeakElement(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]的区间左端点，也是最终结果。
代码实现
class Solution {
public:
int findMin(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。
代码实现
class Solution {
public:
int takeAttendance(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;
}
};
到这里本篇文章内容就结束了，感谢各位大佬的支持