公众号关注推广_公司网站手机版_新乡网站seo_百度seo 优化

⼆分算法是我觉得在基础算法篇章中最难的算法。⼆分算法的原理以及模板其实是很简单的，主要的难点在于问题中的各种各样的细节问题。因此，⼤多数情况下，只是背会⼆分模板并不能解决题⽬，还要去处理各种乱七⼋糟的边界问题

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

查找初始位置

a[mid] >= t  ->  right = mid
a[mid] < t   ->  left = mid + 1

1. while循环里的判断如何写？
   while (left < right)
while (left <= right)
   选择第一个，因为第二个有可能会导致死循环
2. 求中点的方式
   (left + right) / 2
(left + right + 1) / 2
   选第一个，因为第二个有可能会导致死循环
3. 二分之后，相遇点的情况
   需要判断一下，循环结束后，是否是想要的结果

查找终止位置

a[mid] <= t  ->  left = mid
a[mid] > t   ->  right = mid - 1

1. while循环里的判断如何写？
   while (left < right)
while (left <= right)
   选择第一个，因为第二个有可能会导致死循环
2. 求中点的方式
   (left + right) / 2
(left + right + 1) / 2
   选第二个，因为第一个有可能会导致死循环
3. 二分之后，相遇点的情况
   需要判断一下，循环结束后，是否是想要的结果

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();//处理边界情况if (n == 0) return {-1, -1};//求起始位置int left = 0, right = n - 1;while (left < right){int mid = (left + right) / 2;if (nums[mid] >= target) right = mid;else left = mid + 1;}//left或者right所指的位置有可能是最终结果if (nums[left] != target) return {-1, -1};int retleft = left; //记录起始位置//求终止位置left = 0, right = n - 1;while (left < right){int mid = (left + right + 1) / 2;if (nums[mid] <= target) left = mid;else right = mid - 1;}return {retleft, left};}
};

模板

⼆分的模板在⽹上⾄少能搜出来三个以上。但是，我们仅需掌握⼀个，并且⼀直使⽤下去即可

// ⼆分查找区间左端点  
int l = 1, r = n;  
while(l < r)  
{  int mid = (l + r) / 2;  if(check(mid)) r = mid;  else l = mid + 1;  
}  
// ⼆分结束之后可能需要判断是否存在结果

// ⼆分查找区间右端点  
int l = 1, r = n;  
while(l < r)  
{  int mid = (l + r + 1) / 2;  if(check(mid)) l = mid;  else r = mid - 1;  
}  
// ⼆分结束之后可能需要判断是否存在结果

为了防⽌溢出，求中点时可以下⾯的⽅式：

• mid = l + (r - l) / 2

时间复杂度

每次⼆分都会去掉⼀半的查找区域，因此时间复杂度为logN

模板记忆⽅式

1. 不⽤死记硬背，算法原理搞清楚之后，在分析题⽬的时候⾃然⽽然就知道要怎么写⼆分的代码；
2. 仅需记住⼀点，if/else 中出现-1 的时候，求mid 就+1就够了。

⼆分问题解决流程

1. 先画图分析，确定使⽤左端点模板还是右端点模板，还是两者配合⼀起使⽤；
2. ⼆分出结果之后，不要忘记判断结果是否存在，⼆分问题细节众多，⼀定要分析全⾯。

STL中的⼆分查找

<algorithm>

1. lower_bound ：⼤于等于x的最⼩元素，返回的是迭代器；时间复杂度：O(log N) 。
2. upper_bound ：⼤于x的最⼩元素，返回的是迭代器。时间复杂度：O(log N) 。
   ⼆者均采⽤⼆分实现。但是STL中的⼆分查找只能适⽤于"在有序的数组中查找"，如果是⼆分答案就不能使⽤。因此还是需要记忆⼆分模板

牛可乐和魔法封印

找大于等于x的起始位置

a[mid] >= x  ->  right = mid
a[mid] < x   ->  left = mid + 1

直接用(left+right)/2
循环结束之后的位置：

if (a[left] < x)  //返回0

找小于等于y的位置

a[mid] <= y  ->  left = mid
a[mid] > y   ->  right = mid - 1

直接用(left+right+1)/2
循环结束之后的位置：

if (a[left] > y)  //返回0

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int n;
int a[N];int binary_search(int x, int y)
{//大于等于xint left = 1, right = n;while (left < right){int mid = (left + right) / 2;if (a[mid] >= x) right = mid;else left = mid + 1;}if (a[left] < x) return 0;int tmp = left;//小于等于yleft = 1, right = n;while (left < right){int mid = (left + right + 1) / 2;if (a[mid] <= y) left = mid;else right = mid - 1;}if (a[left] > y) return 0;return left - tmp + 1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];int Q; cin >> Q;while (Q--){int x, y; cin >> x >> y;cout << binary_search(x, y) << endl;}return 0;
}

P1102 A-B 数对 - 洛谷

STL的使⽤

1. lower_bound ：传⼊要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值k，然后返回该数组中>=k的第⼀个位置；
2. upper_bound：传⼊要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值k，然后返回该数组中>k的第⼀个位置；
   ⽐如：a = [10, 20, 20, 20, 30, 40]，设下标从1 开始计数，在整个数组中查询20 ：
3. lower_bound(a + 1, a + 1 + 6, 20) ，返回a + 2 位置的指针；
4. upper_bound(a + 1, a + 1 + 6, 20) ，返回a + 5 位置的指针；
5. 然后两个指针相减，就是包含20 这个数区间的⻓度

• STL的使⽤范围很「局限」，查询「有序序列」的时候才有⽤，数组⽆序的时候就⽆法使
  ⽤。但是⼆分模板也能在「数组⽆序」的时候使⽤，只要有「⼆段性」即可

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 2e5 + 10;LL n, c;
LL a[N];
unordered_map<int, int> mp;int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> c;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1, a+1+n);LL ret = 0;for (int i = 2; i <= n; i++){LL b = a[i] - c;ret += upper_bound(a+1, a+i, b) - lower_bound(a+1, a+i, b);}cout << ret << endl;return 0;
}

P1678 烦恼的高考志愿 - 洛谷

a[mid] >= b  ->  right = mid;
a[mid] < b   ->  left = mid + 1;

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e5 + 10;
int n, m;
int a[N];int find(LL b)
{int left = 1, right = m;while (left < right){int mid = (left + right ) / 2;if (a[mid] >= b) right = mid;else left = mid + 1;}return left;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> m >> n;for (int i = 1; i <= m; i++) cin >> a[i];sort(a + 1, a + 1 + m);//加左右护法a[0] = -1e7 + 10;LL ret = 0;for (int i = 1; i <= n; i++){LL b; cin >> b;        int pos = find(b);ret += min(abs(a[pos] - b), abs(a[pos-1] - b));}cout << ret << endl;return 0;
}