Pixiv - Miracle
3-查找
733 字
4 分钟
3-查找
查找
二分查找
int binarySeach (vector<int> arr, int target) { int l = 0, r = arrs.size();
while (l < r) { int m = (l + r) >> 1;
if (arr[m] > target) { r = m;// j及其右边都是>target的； } else { l = m + 1;// i左边都是<=target的，本身不一定 } } // 由于每次只有i走一步或j走一步，故一定满足终止条件l==r, 设这个值为k // k左边都是<=target的，本身及其右边都是>target的 // 故k - 1是<=target的索引中的最大值，k是 > target 的索引中的第一个值
// 适用于非法/合法的数组段 return l;}规律
i<j情况下的二分查找的正确性取决于
升序找>= target的第一个数
(n - 1, j取等，中点偏左)
升序找>= target的最后一个数
(n - 1, i取等，中点偏右)
升序找>= target的第一个数 && 降序找<=target的第一个数 = (n - 1, j取等，中点偏左)，答案为i=j
| 大小序 | 条件 | 位置 | 过程 | |
|---|---|---|---|---|
| 升序+ | >= target+ || > target+ | 第一个数 | (0n, j取等，中点偏左) | |
| 升序+ | <= target- || < target- | 最后一个数 | (-1n-1, i取等，中点偏右) | |
| 降序- | <= target- || < target- | 第一个数 | (0n, j取等，中点偏左) | |
| 降序- | >= target+ || > target+ | 最后一个数 | (-1n-1, i取等，中点偏右) |
如果将左规定为合法，右规定为非法，则大小序和条件异号的二分查找，直接输出所需值i
二分查找不能自然处理空集，会返回-1
对于i<=j的终止条件，无非是i = j+1，j满足条件，i一定不满足条件，迭代方式为i + 1, j - 1，其余和i<j类似
| 大小序 | 条件 | 位置 | 过程 |
|---|---|---|---|
| 升序+ | >= target+ || > target+ | 第一个数 | (0n-1, j取等，中点偏左，答案i) |
| 升序+ | <= target- || < target- | 最后一个数 | (0n-1, i取等，中点偏右，答案j) |
| 降序- | <= target- || < target- | 第一个数 | (0n-1, j取等，中点偏左，答案i) |
| 降序- | >= target+ || > target+ | 最后一个数 | (0n-1, i取等，中点偏右，答案j) |
总结
- 是否取等决定初始值是n还是n-1
- 是大于还是小于决定是j取等还是i取等，中点是偏左还是偏右
#include <iostream>#include <vector>
using namespace std;
int binarySearch(vector<int> arr, int target) { int i = 0, j = arr.size();
while (i < j) { int m = (i + j) >> 1;
if (arr[m] > target) { j = m; } else { i = m + 1; } }
return j;}用途
- 用于查找第k个数（至少有k个数和该数合法中最小的数）
- 二分答案最大值/最小值
分层
分层索引
int r = 0;int s = 0;while (s < n) { ++r; s += r;}s -= r;
int idx = n - s;文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
随机文章 随机推荐