【1】69. x 的平方根 - 力扣（LeetCode）
🍡解题思路：首先想到的是暴力查找，从1开始依次比较x与num*num的大小，然后找出满足num*num<=x且(num+1)*(num+1)>x的num值；再来看看能不能优化一下，因为是有序的比较，因此可以考虑使用二分查找算法来解决此题。
🍡算法原理：首先找出二段性，观察发现，所求出算数平方根只保留整数部分，因此可以将结果值划分到左段，将num*num<=x的划分为一段，num*num>x的划分为另一段，根据我之前发过的二分查找算法模板介绍的博客(【二分查找】模板+例题)，可以发现这就是典型的查找右端点的二分查找算法，找出条件判断语句的判断条件即可求解
🍡解题步骤：
1）定义左右边界left,right
2）定义循环判断条件left<right
3）设置mid值，由于是右端点二分查找算法，因此是mid=left+(right-left+1)/2（不清楚为什么的可以看看【二分查找】模板+例题）
4）编写条件判断语句：
1.若mid*mid<=x,left=mid
2.若mid*mid>x,right=mid-1
细节处理：由于题目是从0开始的，因此小于1的
注意：由于题目给出的数字范围太大，可能会出现溢出情况，因此mid用longlong类型，left和right也可以设置成longlong类型；
🍡实现代码：
int mySqrt(int x) {
if(x<1)
return 0;
int left=1;
int right=x;
while(left<right)
{
long long mid=left+(right-left+1)/2;
if(mid*mid<=x)
{
left=mid;
}
else if(mid*mid>x)
{
right=mid-1;
}
}
return left;
}【2】35. 搜索插入位置 - 力扣（LeetCode）
🍡解题思路：首先想到暴力查找，依次比较nums[i]与target的大小，如果nums[i]>=target那么就输出对应位置下标，但是题目要求时间复杂度为O(logN)，因此考虑使用二分查找算法解决
🍡算法原理：可以发现数组的二段性，将数组划分为x<target和x>=target两部分，要求解包含在x>=target部分，很明显是寻找左端点的二分查找
🍡解题步骤：
1）定义左右边界left,right
2）定义循环判断条件left<right
3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2
4）编写条件判断语句：
1.若nums[mid]<target,left=mid+1
2.若nums[mid]>=target,right=mid
细节处理：如果target的值比nums中所有元素都要大，插入位置就是nums.size()，即nums的下一个位置的下标；如果不单独写，输出的就是nums最后一个位置下标，是错误的。
🍡实现代码：
int searchInsert(vector<int>& nums, int target) {
int sz=nums.size();
if(target<nums[0])
{
return 0;
}
else if(target>nums[sz-1])
{
return sz;
}
int left=0;
int right=sz-1;
int mid=0;
while(left<right)
{
mid=left+(right-left)/2;
if(nums[mid]>=target)
{
right=mid;
}
else if(nums[mid]<target)
{
left=mid+1;
}
}
return right;
}【3】852. 山脉数组的峰顶索引 - 力扣（LeetCode）
🍡解题思路：题目要求的峰值元素，比左右两侧的元素都要大，因此可以通过比较相邻元素的大小来确定峰值元素位置
🍡算法原理：寻找二段性，会发现峰值左侧元素都是比它下一个元素小，峰值右侧（包含峰值在内）都是比它下一个元素大；这样就划分出了二段性，会发现是寻找左端点的二分查找算法。
（同理，也可以通过将当前元素与上一个元素比较，将峰值划分在左侧，通过寻找右端点的二分查找算法求解）
🍡解题步骤：
1）定义左右边界left,right
2）定义循环判断条件left<right
3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2
4）编写条件判断语句：
1.若arr[mid]<arr[mid+1],left=mid+1
2.若arr[mid]>arr[mid+1],right=mid
🍡实现代码：
int peakIndexInMountainArray(vector<int>& arr) {
int left=0;
int right=arr.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]>arr[mid+1])
{
right=mid;
}
else if(arr[mid]<arr[mid+1])
{
left=mid+1;
}
}
return left;
}【4】162. 寻找峰值 - 力扣（LeetCode）
🍡解题思路：可以分为三种情况：
1、完全上升趋势
2、完全下降趋势
3、波折曲线
三种情况能找到峰值，因为nums的左侧趋向于-∞，右侧趋向于+∞；如果是情况1，那么最右侧元素就是峰值；如果是情况2，那么最左侧元素就是峰值；如果是情况3可以找到其中一个峰值。观察发现，若nums[i]>nums[i+1]，那么该值右侧呈现下降趋势，而nums最左侧趋向于-∞，因此该值左侧一定存在一个峰值；而当nums[i]<nums[i+1]，同理该值右侧一定存在一个峰值
🍡算法原理：通过上述分析，可以得到二段性，当nums[i]>nums[i+1]（包含峰值元素在内）时，向左搜索；当nums[i]<nums[i+1]时，向右搜索。因此可以使用左端点的二分查找算法
🍡解题步骤：
1）定义左右边界left,right
2）定义循环判断条件left<right
3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2
4）编写条件判断语句：
1.若nums[mid]<nums[mid+1],left=mid+1
2.若nums[mid]>=nums[mid+1],right=mid
🍡实现代码：
int findPeakElement(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]>nums[mid+1])//找出二段性
{
right=mid;
}
else if(nums[mid]<nums[mid+1])
{
left=mid+1;
}
}
return left;
}【5】153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
🍡解题思路：旋转之后变为两段升序数组，通过观察找到二段性，利用二分查找求解
🍡算法原理：可以发现旋转之后AB段的元素都比最后一个元素D的值大，而CD段元素（包含最小值在内）都比元素D的值小；因此划分出二段性。可以发现可利用左端点的二分查找求解
🍡解题步骤：
1）定义左右边界left,right
2）定义循环判断条件left<right
3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2
4）编写条件判断语句：
1.若nums[mid]>nums[sz],left=mid+1
2.若nums[mid]<=nums[sz],right=mid
🍡实现代码：
int findMin(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
int sz=nums.size();
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]>nums[sz-1])
{
left=mid+1;
}
else
{
right=mid;
}
}
return nums[right];
}【6】LCR 173. 点名 - 力扣（LeetCode）
🍡解题思路：可以求解的方式有很多，可以通过累加和的方式求解，也可以通过元素与下标待遇比的方式求解。同样也能用二分查找的方式求解
🍡算法原理：寻找二段性，可以发现缺失值左侧元素的下标值都和元素值相等，而右侧元素的下标值都和元素值不相等，因此根据这个特性划分出二段性
🍡解题步骤：
1）定义左右边界left,right
2）定义循环判断条件left<right
3）设置mid值，如果是右端点二分查找算法，因此是mid=left+(right-left)/2
4）编写条件判断语句：
1.若records[mid]==mid,left=mid+1
2.若records[mid]!=mid,right=mid
细节：右端点二分查找和左端点二分查找都行，要不就是插入元素左侧要不就是插入元素右侧，只需要最后返回的时候判断一下即可。可能存在records=[1,2,3]这种情况，定位在第一个元素;存在records=[0,1,2,3]这种情况，定位在最后一个元素的下一个；如果这两种情况单独考虑，那么使用右端点二分，就可以return left+1；而使用左端点二分，就可以return left-1;
为了方便起见，可以直接判断一下while结束之后在插入元素左侧还是右侧再来确定返回值即可
🍡实现代码：
int takeAttendance(vector<int>& records) {
int left=0;
int right=records.size()-1;
//找出二段性，缺失值左侧都是等于下标，右侧都是！=下标
while(left<right)
{
int mid=left+(right-left+1)/2;
if(records[mid]!=mid)
right=mid-1;
else
left=mid;
}
return left==records[left]?(left+1):left;
//如果是缺失值左侧元素，left+1就是缺失值；如果是缺失值右侧元素，那么left就是缺失值
} int takeAttendance(vector<int>& records) {
int left=0;
int right=records.size()-1;
if(records[0]!=0) return 0;
if(records[right]==right) return right+1;
//找出二段性，缺失值左侧都是等于下标，右侧都是！=下标
while(left<right)//左端点的二分
{
int mid=left+(right-left+1)/2;
if(records[mid]!=mid)
right=mid-1;
else
left=mid;
}
//return left==records[left]?(left+1):left;
return left+1;
} int takeAttendance(vector<int>& records) {
int left=0;
int right=records.size()-1;
if(records[0]!=0) return 0;
if(records[right]==right) return right+1;
//找出二段性，缺失值左侧都是等于下标，右侧都是！=下标
while(left<right)//右端点的二分
{
int mid=left+(right-left)/2;
if(records[mid]!=mid)
right=mid;
else
left=mid+1;
}
//return left==records[left]?(left+1):left;
return left;
}