162. 寻找峰值
162. 寻找峰值 - 力扣（LeetCode）
对于所有有效的 i 都有 nums[i] != nums[i + 1]
解法一：暴力解法
从第一个位置一直向后走，然后分情况即可
1. 第二个元素就往下降，那么第一个元素就是峰顶
2. 一直遍历，直到找到下一个元素比前一个元素小
3. 一直遍历没发现下一个元素比前一个元素小，这时返回最后一个元素
时间复杂度：O(N)
解法二：优化暴力解法 - 二分查找
i i+1
------------*-*-----------
1. arr[i] > arr[i+1]
那么此时是一个下降趋势，那么在左边区间一定存在一个峰值，一定存在最终结果
右边不一定，接下来在左边寻找
2. arr[i] < arr[i+1]
那么此时是一个上升趋势，那么在右边区间一定存在一个峰值
左边不一定，接下来在右边寻找
此时发现二段性，可以把数组分成两部分
第一种情况：arr[mid] > arr[mid+1] -> right = mid(包含i，i也可能是峰值)
第二种情况：arr[mid] < arr[mid+1] -> left = mid + 1
代码：C++
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;
}
};153. 寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
解法一：暴力查找最小值
[3,4,5,1,2]
从前往后遍历即可
时间复杂度：O(N)
[3,4,5,1,2]
可以分解为两段，一段有上升趋势，峰值过后的那一段也是上升趋势
解法二：二分查找
二段性：
B
/
/
/
A
--------------------------------------------------------
D
/
/
/
C
AB这段区域是严格大于D点这个值的
CD这段区域是严格小于等于D点这个值的
1. AB这段区域: nums[i] > nums[n-1]
2. CD这段区域: nums[i] <= nums[n-1]
如果是第一种情况：nums[mid] > nums[n-1] -> left = mid + 1
当落在AB的时候没有要找的结果，所以要到右边去找
如果是第二种情况：nums[mid] <= nums[n-1] -> right = mid
mid落在CD，去左边区域寻找，但是right不能越过C点
最后会停在c点，c点就是最小值
代码：C++
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
int x = nums[right];
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] > x) left = mid + 1;
else right = mid;
}
return nums[left];
}
};剑指 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
解法一：哈希表
解法二：直接遍历找结果
解法三：位运算
用^异或运算
比如[0, 1, 2, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
拿正常数组的数和没有缺少的数组通通异或在一起，相同的数会抵消，最后异或的结果就是缺少的数
解法四：高斯求和公式 - 等差数列
算一下没有缺少这批数的和，首项+末项的和/2
然后依次减去数组中的数，最后的数就是缺失的数
上方四组的时间复杂度都是O(N)
更优的解法，解法五：二分查找
[0, 1, 2, | 4, 5, 6]
index:
[0, 1, 2, | 3, 4, 5]
|左边的值一一对应，右边不对应
所以有二段性
要找的结果就是右边区域的最左边的元素的下标
1. 落在左边区间，值和下标对应：nums[mid] = mid -> left = mid + 1
去右边寻找，因为这个区域一定没有结果
2. 落在右边区间：nums[mid] != mid -> right = mid
细节问题：边界情况
如果数组是[0, 1, 2, 3]，下标也是一样的
缺失的元素是后面的4，现在根本不存在右边的区间
最终返回的时候要判断一下，当 left==right，所指的值跟下标相等，要返回的是+1
代码：C++
int missingNumber(vector<int>& nums)
{
// 解法五，二分查找
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == mid) return left = mid + 1;
else right = mid;
}
// 返回结果，处理细节问题
return nums[left] == left ? left + 1 : left;
}
