1. 山脉数组的峰顶索引
题目描述：
示例：
题目链接： 山脉数组的峰顶索引
题解：
第一步：
首先确定二段性，把顶峰放到左区间还是右区间取决于你自己，会根据取法不同而导致代码不同，但是都能求出顶峰索引。这里我们放到左区间。
第二步：
按照我们的划分方式，要确保左边区间不会越过分界，右边区间同理，就要用 mid 和 mid-1 这种划分方式。如果在左区间，那么 mid 会有等于峰顶索引，即 left = mid；如果在右区间，mid 及其后面的值都不可能是峰顶索引，即 right = mid - 1。
细节问题：
对于二分查找进阶模版，如果在 if 语句的函数体里有减法操作时，那么计算 mid 的公式就要 +1。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (arr[mid] > arr[mid - 1]) {
left = mid;
} else {
right = mid - 1;
}
}
return right;
}
};
2. 寻找峰值
题目描述：
示例：
题目链接： 寻找峰值
题解：
第一步：
首先确定二段性，可以分为在上坡或者下坡，其实这道题和山脉数组的峰顶索引是一样的，这里我们顶峰放在右区间里。
第二步：
按照我们的划分方式，要确保右边区间不会越过分界，左边区间同理，就要用 mid 和 mid+1 这种划分方式。如果在右区间，那么 mid 会有等于峰顶索引，即 right = mid；如果在左区间，mid 及其前面的值都不可能是峰顶索引，即 left = mid + 1。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
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]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};
3. 寻找旋转排序数组中的最小值
题目描述：
示例：
题目链接： 寻找旋转排序数组中的最小值
题解：
第一步：
根据画图，似乎不太好确认二段性，但我们可以发现以 D 点为分界点，左区间的数（A 到 B）都大于 D，右区间的数（C 到 D）都小于 D，那么由此就能确定二段性，不断向中寻找最小的数。
第二步：
如果在右区间，那么 mid 会有等于最小值，即 right = mid；如果在左区间，mid 及其前面的值都不可能是最小值，即 left = mid + 1。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
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[right];
}
};
4. 点名
题目描述：
示例：
题目链接： 点名
题解：
第一步：
在连续数组的前提下，缺失数字的位置开始下标与实际值不同，很明显二段性立马就出来了。
第二步：
如果在右区间，那么 mid 会有等于缺失值的实际位置索引，即 right = mid；如果在左区间，mid 及其前面的值都不可能是缺失值的实际位置索引，即 left = mid + 1。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int takeAttendance(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;
}
};
