冀以尘雾之微补益山海，萤烛末光增辉日月。
前言
这是我自己学习蓝桥杯算法的第三篇博客总结。
上一期笔记是关于滑动窗口算法，没看的同学可以过去看看：
【数据结构与算法】滑动窗口算法_c++滑动窗口算法-CSDN博客https://blog.csdn.net/hsy1603914691/article/details/146181746?sharetype=blogdetail&sharerId=146181746&sharerefer=PC&sharesource=hsy1603914691&spm=1011.2480.3001.8118
技巧
基础模板
1. 定义两个指针来表示两边端点，left--->左端点，right--->右端点。
2. 二分查找的区间为[left,right]，闭区间内任意一点都为未知数。
3. 循环的判断结束条件为left<=right，时间复杂度为O(logN)。
4. 为了防止整数溢出，可以使用mid=left+(right-left)/2或mid=left+(right-left+1)/2。
5. 当数组中元素的个数为偶数时，left+(right-left)/2求出的是偏左的中点，left+(right-left+1)/2求出的是偏右的中点；当数组中元素的个数为奇数时，两者都是正好找到中点。
6. 适用二分查找的情况：数组具备二段性，而非单调性。所以二分查找的重点是去发现数组的二段性。
while(left<=right)
{
int mid=left+(right-left)/2;
if(nums[mid]>target)
right=mid-1;
else if(nums[mid]<target)
left=mid+1;
else
return mid;
}左查找模板
1. 定义两个指针来表示两边端点，left--->左端点，right--->右端点。
2. 二分查找的区间为[left,right]，闭区间内任意一点都为未知数。
3. 循环的判断结束条件为left<right，不能取等号(会陷入死循环)，时间复杂度为O(logN)。
4. 为了防止整数溢出，只能使用mid=left+(right-left)/2，不能使用mid=left+(right-left+1)/2(会陷入死循环)。
5. 查找左端点，right必须承担等号；查找右端点，left必须承担等号。
6. 若两种情况均未触发+1或-1操作，算法将在left==right-1时，进入无限循环状态。
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<target)
left=mid+1;
else
right=mid;
}
//跳出循环时:left==right
if(nums[left]==target)
return left;右查找模板
1. 定义两个指针来表示两边端点，left--->左端点，right--->右端点。
2. 二分查找的区间为[left,right]，闭区间内任意一点都为未知数。
3. 循环的判断结束条件为left<right，不能取等号(会陷入死循环)，时间复杂度为O(logN)。
4. 为了防止整数溢出，只能使用mid=left+(right-left+1)/2，不能使用mid=left+(right-left)/2(会陷入死循环)。
5. 查找左端点，right必须承担等号；查找右端点，left必须承担等号。
6. 若两种情况均未触发+1或-1操作，算法将在left==right-1时，进入无限循环状态。
while(left<right)
{
int mid=left+(right-left+1)/2;
if(nums[mid]=<target)
left=mid;
else
right=mid-1;
}
//跳出循环时:left==right
if(nums[right]==target)
return right;例题
1. leetcode-704题：
704. 二分查找 - 力扣（LeetCode）
class Solution {
public:
int search(vector<int>& nums, int target)
{
int left=0,right=nums.size()-1;
while(left<=right)
{
int mid=left+(right-left)/2;
if(target<nums[mid])
right=mid-1;
else if(target>nums[mid])
left=mid+1;
else
return mid;
}
return -1;
}
};2. leetcode-34题：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
vector<int> v;
int left=0,right=nums.size()-1;
if(nums.size()==0)
return {-1,-1};
while(left<right)//找左端点
{
int mid=left+(right-left)/2;
if(nums[mid]<target)
left=mid+1;
else
right=mid;
}
if(nums[left]==target)
v.push_back(left);
else
return {-1,-1};
left=0,right=nums.size()-1;
while(left<right)//找右端点
{
int mid=left+(right-left+1)/2;
if(nums[mid]>target)
right=mid-1;
else
left=mid;
}
if(nums[right]==target)
v.push_back(right);
else
return {-1,-1};
return v;
}
};3. leetcode-69题：
69. x 的平方根 - 力扣（LeetCode）
class Solution {
public:
int mySqrt(int x)
{
int i=0;
while(1)
{
if((long long)i*i<=(long long)x&&(long long)(i+1)*(i+1)>(long long)x)
return i;
i++;
}
}
};class Solution {
public:
int mySqrt(int x)
{
if(x<1)
return 0;
long long left=0,right=x;
while(left<right)
{
long long mid=left+(right-left+1)/2;
if(mid*mid<=x)
left=mid;
else
right=mid-1;
}
return left;
}
};4. leetcode-35题：
35. 搜索插入位置 - 力扣（LeetCode）
class Solution {
public:
int searchInsert(vector<int>& nums, int target)
{
if(target>nums[nums.size()-1])
return nums.size();
int left=0,right=nums.size()-1;
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;
}
return right;
}
};5. leetcode-852题：
852. 山脉数组的峰顶索引 - 力扣（LeetCode）
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int left=0,right=arr.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]>arr[mid+1])
right=mid;
else
left=mid;
if(left==right-1)
break;
}
if(arr[left]<arr[right])
return right;
else
return left;
}
};class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int left=0,right=arr.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]>arr[mid+1])
right=mid;
else
left=mid+1;
}
return left;
}
};6. leetcode-162题：
162. 寻找峰值 - 力扣（LeetCode）
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;
}
};7. leetcode-162题：
class Solution {
public:
int findMin(vector<int>& nums)
{
if(nums.size()==1)
return nums[0];
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]>nums[mid+1])
{
right=mid+1;
break;
}
else if (nums[mid]>nums[0])
left=mid+1;
else
right=mid;
}
int ret=min(nums[right],nums[0]);
return ret;
}
};class Solution {
public:
int findMin(vector<int>& nums)
{
if(nums.size()==1)
return nums[0];
int left=0,right=nums.size()-1;
int x=nums[nums.size()-1];
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]>x)
left=mid+1;
else
right=mid;
}
return nums[right];
}
};8. leetcode-173题：
LCR 173. 点名 - 力扣（LeetCode）
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;
}
if(records[right]==right)
return right+1;
else
return right;
}
};致谢
感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！