二分查找 c++模板

2026/07/20新补充记住一点即可:二分法是找到第一个大于等于target的位置while(left right) { int mid (left right)/2; int x nums[mid]; if(x target){ ans mid; r mid - 1; }else l mid 1; } return ans;比如说这个例子:35. 搜索插入位置1)如果什么方法都不用,直接暴力去算:class Solution { public: //找到第一个大于等于target的位置 int searchInsert(vectorint nums, int target) { int n nums.size(); for(int i 0 ; i n ; i) { if(nums[i] target)return i; } return n; } };2)如果使用二分class Solution { public: //找到第一个大于等于target的位置 int searchInsert(vectorint nums, int target) { int n nums.size(); int ans n; int l 0 , r n-1; while(l r) { int mid (l r)/2; int x nums[mid]; if(x target) { ans mid; r mid - 1; }else { l mid 1; } } return ans; } };先说体会:二分法中无论是rmid-1还是lmid1都说明mid不是我们要的答案所以我们不要它,将它减去或者略过。如果是lmid或者rmid说明mid还有用以下为两个重要模板二分法其实是不断逼近x,我们假设q[ ]数组是从小到大排列的模板1:while(lr){intmidlr1;if(q[mid]x)rmid;//这个r可以用来求出来的是x的最小值(优先求出)elselmid1;}//如果不存在x的最小值,这个r求出来的是x的最大值(其次求出)模板2while(lr){intmidlr11;if(q[mid]x)lmid;//这个l可以用来求出来的是x的最大值(优先求出)elsermid-1;}//如果不存在x的最大值,这个l求出来的是x的最小值(其次求出)2022-11-20的力扣320场周赛的第二题,完美的使用了以上的模板6242. 二叉搜索树最近节点查询/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:vectorvectorintclosestNodes(TreeNode*root,vectorintqueries){if(!root)return{{-1,-1}};vectorintv;vectorvectorintans;queueTreeNode*q;q.push(root);//下面这个while循环就是宽搜框架while(q.size()){intlenq.size();//这个一层的元素个数for(inti0;ilen;i){autotq.front();//每次拿到这个一行的第i个元素v.push_back(t-val);q.pop();//接下来,我们来扩展一下队列,为下一层宽搜作准备if(t-left)q.push(t-left);if(t-right)q.push(t-right);}}sort(v.begin(),v.end());//我们模拟的单调队列for(inti0;iqueries.size();i){intl0,rv.size()-1;//队头和队尾while(lr){//求queries[i]的最小值intmidlr1;if(v[mid]queries[i])rmid;elselmid1;}inttmpr;l0,rv.size()-1;//队头和队尾while(lr){//求queries[i]的最大值intmidlr11;if(v[mid]queries[i])lmid;elsermid-1;}intleftv[l],rightv[tmp];if(v[tmp]queries[i])right-1;if(v[l]queries[i])left-1;ans.push_back({left,right});}returnans;}};再来一题AcWing 789. 数的范围算法基础课再来一题LeetCode 33. 搜索旋转排序数组LeetCode究极班再来一题6367. 求出最多标记下标再来一题AcWing 1236. 递增三元组补充