二分查找（2）
目录
x 的平方根
题解：
山脉数组的峰顶索引（数组内只有一个峰值）
题解：
寻找峰值（数组内有多个峰值）
题解：
寻找旋转排序数组中的最小值
题解：
点名
题解：
怎么判断 left = mid 、left = mid+1 （right = mid、right = mid -1 ）？
如果 mid 位置可能存在正确答案，那么 mid 位置不能舍去（left = mid ，right = mid）；
如果 mid 位置一定不是正确答案，则 mid 位置要舍去（left = mid+1 、right = mid -1 ）！
x 的平方根
69. x 的平方根 - 力扣（LeetCode）
https://leetcode.cn/problems/sqrtx/description/
题解：
由于求的是 x 的平方根的整数部分，假设 x 的平方根的整数部分为 ret，则 [ 1 , ret ] 区间内的数的平方一定小于等于 x，[ ret+1 , x ] 区间内的数的平方一定大于 x。根据这个二段性我们可以用二分查找解决本题。
假设初始时 left = 1，right = x，
- 如果 mid*mid > x ，right = mid-1，mid 位置需要舍去 ;
- 如果 mid*mid <= x , left = mid，mid 的平方可能是正确答案，该位置不可以舍去.
- 由于 right = mid-1 （不是 mid），所以 mid = left + (right - left+1)/2 .
- 当 left 和 right 相遇时（指向同一个位置），该位置就是正确答案。
为什么 left 和 right 相遇时就是正确答案呢？
假设一开始 left 、mid、right 连续且相邻，此时 x 的平方根的整数部分就在这三个数之中！
如果 mid*mid > x，那么 right 就会和 left 指向同一个位置，而 left*left <= x，比 left 小的数的平方（即 left 左边的数的平方）一定小于 x，left 的平方最接近 x，没有继续迭代的必要了（继续迭代的话，要么 mid*mid <= x ，left = mid，进入死循环，要么 mid*mid > x ，right = mid-1，right 跑到 left 的左边，right*right < x，违背了 right*right > x 的原则）此时 x 的平方根就是 left；
如果 mid*mid <= x，走到第 3 步时，出现两种情况，
1、mid*mid <= x（即第 4 步），left = mid，left 和 right 指向同一个位置，同样的，比 left 小的数的平方（即 left 左边的数的平方）一定小于 x，left 的平方最接近 x。
2、mid*mid > x（即第 5 步），right = mid -1，分析见上。
class Solution {
public:int mySqrt(int x) {if(x<1) return 0;int left=1,right=x;while(left<right){long long int mid=left+(right-left+1)/2;if(mid*mid<=x) left=mid;else right=mid-1;}return left;}
};山脉数组的峰顶索引（数组内只有一个峰值）
852. 山脉数组的峰顶索引 - 力扣（LeetCode）https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/
题解：
同样的，可以把山脉数组分为两部分，以峰顶作为分界线，峰顶左边的数（包括峰顶）在不断递增，峰顶右边的数（不包括峰顶）在不断递减。也就是把数组分为递增数组和递减数组！
假设初始时 left = 0，right = arr.size() -1，
利用在递增数组中，后一个数大于前一个数，在递减数组中，后一个数小于前一个数可得：
- 如果 arr[ mid-1 ] >= arr[ mid ] （位于递减数组），right = mid-1，mid 位置需要舍去 ;
- 如果 arr[ mid-1 ] < arr[ mid ] （位于递增数组）, left = mid，mid 的平方可能是正确答案，该位置不可以舍去.
- 由于 right = mid-1 （不是 mid），所以 mid = left + (right - left+1)/2 .
- 当 left 和 right 相遇时（指向同一个位置），该位置就是正确答案。
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-1]<arr[mid]) left=mid;else right=mid-1;}return left;}
};寻找峰值（数组内有多个峰值）
162. 寻找峰值 - 力扣（LeetCode）https://leetcode.cn/problems/find-peak-element/description/
题解：
和上一题一样，峰顶左边的数（包括峰顶）在不断递增，峰顶右边的数（不包括峰顶）在不断递减，也就是把数组分为递增数组和递减数组！由于数组中可能存在多个峰值，也就是说，可以划分为多个递增数组和递减数组。
假设初始时 left = 0，right = nums.size() -1，
利用在递增数组中，后一个数大于前一个数，在递减数组中，后一个数小于前一个数可得：
- 如果 nums[ mid ] > nums[ mid+1 ] （位于递减数组），说明我们当前位于其中一个山脉中，我们就专注于找到当前山脉的峰顶，其他山脉的峰顶我们就不管了，right = mid（mid 位置不可以舍去），把 mid 右边的山脉都忽略掉 ;
- 如果nums[ mid ] <= nums[ mid+1 ] （位于递增数组），同样的也只找当前山脉的峰顶, left = mid+1，mid 位置可以舍去.
- 由于 right = mid （不是 mid -1），所以 mid = left + (right - left)/2 .
- 当 left 和 right 相遇时（指向同一个位置，在峰顶相遇），该位置就是正确答案。
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. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
题解：
原本数组是升序排序的，旋转后，数组就被分成了两个递增数组。
如下图所示，数组被切分后，可以分为两个递增数组，以切分后的数组的最后一个数字 D 为基准，第一个递增数组内的数字都大于 D，第二个递增数组内的数字都小于 D，旋转后的数组的最小值就在第二个递增数组中，利用这个二段性，就解决这道题。
假设初始时 left = 0，right = nums.size() -1 , 基准数为 nums[ n-1 ] （ n=nums.size() ），
- 如果 nums[ mid ] > nums[ n-1 ] ，说明我们现在位于第一个递增数组，left = mid+1，mid 位置要舍掉，向第二个递增数组逼近；
- 如果 nums[ mid ] <= nums[ n-1 ]，说明我们现在位于第二个递增数组，right = mid，向这个数组的最小值逼近，mid 位置不可以舍去。
class Solution {
public:int findMin(vector<int>& nums) {int left=0,right=nums.size()-1,n=nums.size();while(left<right){int mid=left+(right-left)/2;if(nums[mid]>nums[n-1]) left=mid+1;else right=mid;}return nums[left];}
};
点名
LCR 173. 点名 - 力扣（LeetCode）https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
题解：
本道题有多种解法，这里提供二分查找的解决。
根据下图数组可以发现，我们缺的数字是 3 ，比 3 小的数字和数字对应的下标是相等的，比 3 大的数字比数字对应的下标大。缺失数字的右边第一个数字的下标恰好为缺失数字！
根据这个二段性，假设初始时 left =0，right = records.size() -1，
- 如果 records[ mid ] == mid，说明缺失的数字在 mid 的右边，left = mid + 1，mid位置要舍去；
- 如果 records[ mid ] != mid，说明缺失的数字在 mid 的左边，或者就在 mid 位置，所以 mid 位置不能舍去，right = mid。
- 由于 right = mid （不是 mid -1），所以 mid = left + (right - left)/2 .
- 当 left 和 right 相遇时：如果 records[ left ] == left ，说明它们在缺失数字的左边相遇了，则缺失数字为 left+1；如果 records[ left ] != left，说明它们在缺失数字的右边相遇了，则缺失数字为 left。
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;}
};