当前位置：首页 > news >正文

【数据结构与算法】二分查找

news 2025/5/13 12:20:42

冀以尘雾之微补益山海，萤烛末光增辉日月。

前言

这是我自己学习蓝桥杯算法的第三篇博客总结。

上一期笔记是关于滑动窗口算法，没看的同学可以过去看看：
【数据结构与算法】滑动窗口算法_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;elsereturn 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;elseright=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;elseright=mid-1;
}
//跳出循环时:left==right
if(nums[right]==target)return right;

例题

1. leetcode-704题：

704. 二分查找 - 力扣（LeetCode）https://leetcode.cn/problems/binary-search/

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;elsereturn mid;}return -1;}
};

2. leetcode-34题：

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/628784409/

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;elseright=mid;}if(nums[left]==target)v.push_back(left);elsereturn {-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;elseleft=mid;}if(nums[right]==target)v.push_back(right);elsereturn {-1,-1};return v;}
};

3. leetcode-69题：

69. x 的平方根 - 力扣（LeetCode）https://leetcode.cn/problems/sqrtx/

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;elseright=mid-1;}return left;}
};

4. leetcode-35题：

35. 搜索插入位置 - 力扣（LeetCode）https://leetcode.cn/problems/search-insert-position/

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;elseright=mid;}return right;}
};

5. leetcode-852题：

852. 山脉数组的峰顶索引 - 力扣（LeetCode）https://leetcode.cn/problems/peak-index-in-a-mountain-array/

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;elseleft=mid;if(left==right-1)break;}if(arr[left]<arr[right])return right;elsereturn 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;elseleft=mid+1;}return left;}
};

6. leetcode-162题：

162. 寻找峰值 - 力扣（LeetCode）https://leetcode.cn/problems/find-peak-element/submissions/629136551/

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;elseright=mid;}return left;}
};

7. leetcode-162题：

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/submissions/629221865/

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;elseright=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;elseright=mid;}return nums[right];}
};

8. leetcode-173题：

LCR 173. 点名 - 力扣（LeetCode）https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

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;elseright=mid;}if(records[right]==right)return right+1;elsereturn right;}
};