1. 基础二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
暴力解法就是遍历这个数组，找到这个元素就将该元素的下标进行返回，时间复杂度为 O(N)。
我们找到一个数 4，现在要找 target=5，那么 4 比 5 小，那么 4 左边的数字肯定都比 5 小，那么 4 左边的数字我们就不需要去看了。那么我们直接将 4 左边的区间排除，从 4 右边的区间去找。
所以我们的思路就是，在一个数组中随便找一个点，将这个数和 target 进行比较。如果这个数小于 target 的话，那么我们直接从这个数的右边的区间去找；如果这个数比 target 大的话，那么我们从这个数的左边去找。
只要数组具有二段性的话，那么我们就可以使用二分查找算法。我们可以找二分之一的位置，或者三分之一的位置的数，只要能将我们的数组分成两段的话，都是可行的，但是选择中间点的效果是最好的。
因为二分查找的算法是从中间的点去选择是最好的。我们需要频繁地找中点和频繁的找区间，所以我们需要定义三个指针：一个 left 指向数组开始的数，一个 right 指向最后一个数字，一个 mid 指向中间的元素。根据中间点的值和 target 进行比较然后确定我们的区间。
如果我们的 mid < target 的话，那么我们的 left 直接定义到 mid+1 的位置，我们再从 [mid+1, right] 这个区间找中间值去分区间，所以我们二分查找算法是循环式的。
如果我们的 mid > target 的话，那么我们的 right 就需要定义到 mid-1 的位置，那么我们就需要从 [left, mid-1] 的位置开始。
还有一种特殊情况，就是我们的 mid = target，那么我们就直接找到了目标值。
细节问题
- 循环结束的条件：当 left > right，我们就停止循环。
- 时间复杂度：log n。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
// int mid = (left + right) / 2; // 这种求中间值的方法存在溢出的现象
int mid = left + (right - left) / 2; // 这种方式是可以算出中间点的，总长度/2，然后让 left 加上去，那么就得到了我们中间点了，还能防止溢出的
// 分三种情况进行讨论
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else return mid; // 正好找到了结果
}
// 整个 while 循环结束了都没找到的话，那么我们直接返回 -1 就行了
return -1;
}
};
我们这里求中间值的代码是 left + (right - left) / 2，因为这样可以避免溢出的情况出现。
朴素二分查找模版如下：
根据题目的要求往里面填东西。
2. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入： nums = [5,7,7,8,8,10], target = 8 输出： [3,4]
示例 2：
输入： nums = [5,7,7,8,8,10], target = 6 输出： [-1,-1]
示例 3：
输入： nums = [], target = 0 输出： [-1,-1]
给到我们的数组要么是递增的，要么是不变的。
暴力解法就是从开始到末尾，最差的情况下时间复杂度是 O(N)。
朴素二分的话，虽然可以实现这个题，但是时间复杂度不行。
我们这里的话，当 x 小于 t 的话，处理方式和我们朴素二分的方式一样的。
查找区间的左端点
但是当我们的 x >= t 的话，我们需要将我们的 right 定位到我们的 mid 的位置上，因为 mid 可能是左端点的位置。如果我们将 right 定位到 mid-1 的话，恰好此时 Mid 就是我们要找的话，那么就永远找不到 t 了。
细节处理： 循环条件必须是 left < right，不能是 left <= right。 一是因为当 left = right 的时候就是最终的结果。 二是因为我们判断了的话就会陷入死循环了。 如果我们此时 left = right 的话，我们进入到上面的第二个条件了，right = mid，那么此时 right 就会原地不动进行死循环了。
现在我们的求中点的话有两种方式：
left + (right - left) / 2
left + (right - left + 1) / 2
当我们数组元素是偶数的时候的话，我们使用第一种的话，那么我们的中点是相较于靠左的；第二种方法的话就是靠右的。
当我们使用第二种求中点的方式后，当我们数组中只剩下两个数之后，我们的 right 在后续判断中是会陷入死循环的。
所以我们只能使用我们第一种求中点的方法。
查找区间的右端点
当 x <= t 的时候，我们的更新策略是 left = mid。 当 x > t，right = mid - 1。
我们循环条件必须是 left < right，求中点的方式，因为我们这里是求右端点，所以我们求中点的方式是 left + (right - left + 1) / 2。
解决代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 处理数组为空的情况
if (nums.size() == 0) return {-1, -1};
int begin = 0;
// 二分左端点
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
// 此时 left 和 mid 的在循环结束就相遇了
// 判断是否存在结果
if (nums[left] != target) return {-1, -1};
else begin = left;
// 2. 二分右端点
right = nums.size() - 1; // 这里我们重置下右端点就行了，左端点的话不需要动
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] <= target) left = mid;
else right = mid - 1;
}
// 那么出了循环了，此时的两个指针都指向我们的右端点了，那么我们下面直接返回就行了
return {begin, right};
}
};
我们使用两个二分查找来找出我们符合条件的区间。我们先使用二分查找找到我们的左端点，在这个二分中，为了找到我们的左端点，我们的求中点的方式一定要设置为 left + (right - left) / 2，这样的话当我们数组是偶数元素的话，那么我们的 mid 是会落在左边的，在循环结束之后，我们使用 begin 记录我们的左端点的位置。
在第二个二分中，我们去求我们的右端点。
寻找左边界：
- 我们注意到以左边界划分的两个区间的特点：左边区间 [left, resLeft - 1] 都是小于 x 的；右边区间（包括左边界）[resLeft, right] 都是大于等于 x 的。
- 因此，关于 mid 的落点，我们可以分为下面两种情况：当我们的 mid 落在 [left, resLeft - 1] 区间的时候，也就是 arr[mid] < target。说明 [left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，继续在 [mid + 1, right] 上寻找左边界；当 mid 落在 [resLeft, right] 的区间的时候，也就是 arr[mid] >= target。说明 [mid + 1, right]（因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界。
寻右边界：
- 用 resRight 表示右边界；我们注意到右边界的特点：左边区间（包括右边界）[left, resRight] 都是小于等于 x 的；右边区间 [resRight + 1, right] 都是大于 x 的。
- 因此，关于 mid 的落点，我们可以分为下面两种情况：当我们的 mid 落在 [left, resRight] 区间的时候，说明 [left, mid - 1]（mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新 left 到 mid；当 mid 落在 [resRight + 1, right] 的区间的时候，说明 [mid, right] 内的元素是可以舍去的，此时更新 right 到 mid - 1 的位置。
左指针：left = mid，可能会原地踏步（比如：如果向下取整的话，如果剩下 1,2 两个元素，left == 1，right == 2，mid == 1。更新区间之后，left，right，mid 的值没有改变，就会陷入死循环）。 右指针：right = mid - 1，是会向前移动的，因此区间是会缩小的；因此一定要注意，当 right = mid 的时候，要向下取整。
总结二分模版
3. x 的平方根
给你一个非负整数 x，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1:
输入： x = 4 输出： 2
示例 2:
输入： x = 8 输出： 2 解释： 8 的算术平方根是 2.82842…，由于返回类型是整数，小数部分将被舍去。
0 <= x <= 2^31 - 1
我们可以直接利用二分查找进行操作。
class Solution {
public:
int mySqrt(int x) {
if (x < 1) return 0; // 处理边界情况
int left = 1, right = x;
while (left < right) {
// 一段区级上，如果我们的 mid*mid<=x 的话，那么目标肯定在 mid 右边，甚至可能是 mid，我们让 left=mid
// 如果 mid*mid<x 的话，那么肯定是在 mid 左边，我们直接让 right=mid-1 就行了
long long mid = left + (right - left + 1) / 2; // long long 防溢出
if (mid * mid <= x) left = mid;
else right = mid - 1;
}
// 出了循环之后，我们的 mid
return left;
}
};
4. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
如果我们在一段数组中找到了 target 的话，那么我们就返回他的对应下标。如果没有找到的话，那么就返回我们该插入的位置的下标。
我们这里的 target 在数组中找不到，然后我们需要找到他插入的位置，我们将这个数组分成两个区间，左边的就是小于 t 的，右边的就是大于等于 t 的。
那么我们仅仅需要找到大于等于这段区域的左端点就行了，所以现在我们使用查找区间左端点的模版来进行操作。
如果 x < t 的话，x 落在了左边区间里面了，那么结果一定不会在这里的，所以我们是需要让 left 更新为 mid+1，然后在右边的这段区间继续寻找结果，就是 left = mid+1。
如果 x >= t 的话，那么我们就是掉在了第二块区间里面了，我们需要去这段区间的左半边去寻找结果，因为此时的 mid 可能是最终的结果，所有我们直接让 right = mid。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (nums[left] < target) return left + 1; // 就是在末尾了，此时的 left，那么我们直接将 target 插入到 left+1 的位置了
return left;
}
};
5. 山脉数组的峰顶索引
给定一个长度为 n 的整数山脉数组 arr，其中的值递增到一个峰值元素然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入： arr = [0,1,0] 输出： 1
示例 2：
输入： arr = [0,2,1,0] 输出： 1
示例 3：
输入： arr = [0,10,5,2] 输出： 1
这个山峰数组就是先上升后下降，这个题就是让我们找到我们的封顶元素，然后返回对应数据的下标。
当我们在遍历的时候，第一次遇到一个数大于后面的数的话，那么这个数就是峰值，当我们第一次扫描到这个数的时候我们就停止下来。
所以我们的解法一：利用暴力枚举，时间复杂度是 O(N)。
我们将整个数组分成两个部分：arr[i] > arr[i-1] 和 arr[i] < arr[i-1]。那么这里就可以看出二段性了。
如果落在了左边的区间的话，那么我们的 mid 包含最终的结果。arr[mid] > arr[mid-1]，我们这里更新 left = mid (mid 可能是最终的结果)。
落在右边的区间的话，那么这段区域一定不是最终的结果，那么我们直接都忽略掉。arr[mid] < arr[mid-1]，我们这里更新 right = mid - 1。
那么我们取中间值的话，我们就是 left + (right - left + 1) / 2。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1, right = arr.size() - 2; // 因为我们第一个元素和最后一个元素绝对不可能是最终的结果，所以我们就这么设置
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (arr[mid] > arr[mid - 1]) left = mid;
else right = mid - 1;
}
// 二分结束了，那么我们返回这个结果就行了
return left;
}
};
6. 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入： nums = [1,2,3,1] 输出： 2 解释： 3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入： nums = [1,2,1,3,5,6,4] 输出： 1 或 5 解释： 你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5，其峰值元素为 6。
提示：
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
如果第一个值就是 -∞，那么我们直接返回 0 就行了。
暴力解法就是从第一个位置开始走，一直向后走，分情况讨论即可。
现在将整个数组分成两个部分，我们数组开始和结束的位置都是 -∞。
如果我们的 arr[i] > arr[i+1] 的话，那么就说明我们左边区域肯定是存在峰值的，因为从 -∞ 开始的话，我们是上升的，可能是一直上升到 i 的位置，所以这种情况的话左边是存在峰值的，右边的话可能存在峰值。
如果是 arr[i] < arr[i+1] 的话，那么我们左边的话可能不存在峰值，右边区域可能存在峰值了。
我们这道题的话是存在二段性的。
如果 arr[mid] > arr[mid+1] 的话，说明我们左边的这段区域是一定会有结果的，包含 mid，所以我们直接让 right = mid。
如果是 arr[i] < arr[i+1] 的话，说明我们友区间是一定存在结果的，所有我们让 left = mid+1 即可。
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;
}
};
7. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到
[4,5,6,7,0,1,2] - 若旋转 7 次，则可以得到
[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
给你一个元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入： nums = [3,4,5,1,2] 输出： 1 解释： 原数组为 [1,2,3,4,5]，旋转 3 次得到输入数组。
示例 2：
输入： nums = [4,5,6,7,0,1,2] 输出： 0 解释： 原数组为 [0,1,2,4,5,6,7]，旋转 4 次得到输入数组。
示例 3：
输入： nums = [11,13,15,17] 输出： 11 解释： 原数组为 [11,13,15,17]，旋转 4 次得到输入数组。
以这个为例子 [0,1,2,4,5,6,7]，旋转一次就是将 7 挪动到前面了，旋转 2 次就是将 6 挪动到前面了。
解法一：暴力查找最小值，时间复杂度就是 O(N)。
AB 这一段是大于 D 点的值的，CD 这一段是小于等于 D 点的值的。
AB：nums[i] > nums[n-1]
CD：nums[i] <= nums[n-1]
如果落在 AB 区间的话，那么 nums[mid] > nums[n-1]。
- 如果中间元素大于右边的元素，则最小值在右半部分。
- 如果中间元素小于或等于右边元素，则最小值在左半部分或可能是中间元素本身。 不断地利用中间值和 right 对应的值进行比较，因为这个数组在转的时候，第一次是最后一个最大的数字到前面，第二次是最后一个第二大的数字到前面。
如果我们中间元素大于右边的元素的话，那么最小值肯定是出现在在右边的，左边的就是比较大的数字的，那么我们是需要找到最小值的，所以我们需要往右边靠的，因为中间元素大于右边的元素，所以我们直接让 left = mid+1。
但是如果 mid 位置的值小于等于最右边的值的话，那么最小值肯定在左边，甚至可能是 mid 的位置，所以我们让 right = mid。
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
// 此时我们的 left 和 right 相遇的就是最小的元素
return nums[left];
}
};
8. 缺失的第一个正整数
一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n-1 之内。
在范围 0 到 n-1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
数据范围
1 <= n <= 1000
样例
输入：[0,1,2,4] 输出：3
可以利用下面的方法进行求出这个缺失的数，第四种就是利用等差数列求和求出数组总大小，然后依次减去数组中的每个数，最后剩下的就是我们缺失的数。
我们可以将数组分成两个部分，左边的就是数组和下标相等的，右边的数的大小比下标大 1 的，所以我们需要找到我们右边这段区间最左边的这个数的下标就可以知道我们缺失的那个数是什么了。
当我们的 mid 落在左边区域的话，那么我们是需要去右边去寻找的，所以我们需要更新 left = mid+1，这段区间的判断条件是 nums[mid] = mid。
如果落在右边区域的话，那么我们需要往左边靠，找到这个区间的靠左的数，我们需要更新 right = mid，mid 有可能在最终结果上。 右边区间的判断条件是 nums[mid] != mid。
但是存在一种边界的情况。下面的话就是我们缺少了 4，但是循环结束后我们最终会落在 3 这个位置上面的，我们需要的结果是 3 这个位置后面的一位数。
所以我们返回结果的时候需要进行判断下，我们结束的位置的 nums[mid] = mid，说明我们此时的数组是一个完全递增的数组，我们缺失的数就是 mid+1。
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == mid) left = mid + 1; // 落在左边的区间中
else right = mid;
}
// 处理下细节问题
return nums[left] == left ? left + 1 : left; // 如果等于 left 的话就返回 left+1，如果不等于的话就返回 left
}
};
