面试算法笔记
应用介绍
二分查找模板
注意点:
- 是否存在重复元素
模板 1 - binary_search
- 没有重复元素时,目标值若存在,则返回索引;若不存在,返回 -1
- 存在重复元素时,目标值若存在,则返回最小索引;若不存在,返回 -1
模板 2 - lower_bound
- 返回大于、等于目标值的最小索引(第一个大于、等于目标值的索引)
模板 3 - upper_bound
- 返回大于目标值的最小索引(第一个大于目标值的索引)
注意点:
*/
#pragma once
#include "../all.h"
int binary_search(vector<int>& nums, int v) {
if (nums.size() < 1) return - 1;
int lo = -1, hi = nums.size();
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < v)
lo = mid;
else
hi = mid;
}
return nums[lo + 1] == v ? lo + 1 : -1;
}
int lower_bound(vector<int>& nums, int v) {
if (nums.size() < 1) return -1;
int lo = -1, hi = nums.size();
while (hi - lo > 1) { // 退出循环时有:lo + 1 == hi
int mid = lo + (hi - lo) / 2;
if (nums[mid] < v)
lo = mid; // 因为始终将 lo 端当做开区间,所以没有必要 `lo = mid + 1;`
else
hi = mid; // 而在 else 中,mid 可能就是最后的结果,所以不能 `hi = mid - 1`
}
return lo + 1; // 相比 binary_search,只有返回值不同
}
/*为什么返回 `lo+1`,而不是 `hi`?(退出循环时有 lo + 1 == hi)
模板开始时将 (lo, hi) 看做是一个开区间,通过不断二分,最终这个区间中只会含有一个值,即 (lo, hi]
返回 lo+1 的含义是,结果就在 lo 的下一个;
在迭代的过程中,hi 会从开区间变为闭区间,而 lo 始终是开区间,
返回 lo+1 显得更加统一。
当然,这跟迭代的写法是相关的,你也可以使最终的结果区间是 [lo, hi),这取决于个人习惯。
*/
int upper_bound(vector<int>& nums, int v) {
if (nums.size() < 1) return -1;
int lo = -1, hi = nums.size();
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] <= v) // 相比 lower_bound,唯一不同点:`<` -> `<=`
lo = mid;
else
hi = mid;
}
return lo + 1;
}
void
solve()
{
vector<int> v{ 1,2,2,3,4,6,6,6,8,9 };
cout << v.size() << endl; // 10
auto ret = binary_search(v, 7);
cout << ret << endl; // -1
ret = lower_bound(v, 6);
cout << ret << endl; // 5
ret = lower_bound(v, 7);
cout << ret << endl; // 8
ret = upper_bound(v, 6);
cout << ret << endl; // 8
ret = upper_bound(v, 7);
cout << ret << endl; // 8
}
。。。。。。。。想了解详情请下载附件。
©版权声明:本文内容由互联网用户自发贡献,版权归原创作者所有,本站不拥有所有权,也不承担相关法律责任。如果您发现本站中有涉嫌抄袭的内容,欢迎发送邮件至: www_apollocode_net@163.com 进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。
转载请注明出处: apollocode » 面试算法笔记
文件列表(部分)
名称 | 大小 | 修改日期 |
---|---|---|
Algorithm_for_Interview.vcxproj | 2.88 KB | 2018-08-31 |
Algorithm_for_Interview.vcxproj.filters | 2.43 KB | 2018-08-31 |
all.h | 0.44 KB | 2018-08-31 |
main.cpp | 0.41 KB | 2018-08-31 |
test.hpp | 0.18 KB | 2018-08-31 |
Cpp之STL容器.md | 4.30 KB | 2018-08-31 |
Cpp之string专题.hpp | 1.42 KB | 2018-08-31 |
Cpp之常用方法.md | 2.42 KB | 2020-09-08 |
IO模板.hpp | 1.33 KB | 2018-08-31 |
README.md | 0.38 KB | 2018-08-31 |
heap.hpp | 0.89 KB | 2018-08-31 |
list.hpp | 0.77 KB | 2018-08-31 |
map.hpp | 1.14 KB | 2018-08-31 |
queue.hpp | 0.61 KB | 2018-08-31 |
set.hpp | 1.32 KB | 2018-08-31 |
stack.hpp | 0.43 KB | 2018-08-31 |
vector.hpp | 1.13 KB | 2018-08-31 |
不通过继承实现多态.hpp | 0.80 KB | 2018-08-31 |
位运算.hpp | 0.84 KB | 2018-08-31 |
遍历所有子集.hpp | 0.71 KB | 2018-08-31 |
遍历所有正因子.hpp | 0.48 KB | 2018-08-31 |
atoi.hpp | 0.99 KB | 2018-08-31 |
dp-01背包.hpp | 0.21 KB | 2018-08-31 |
二分查找最优解模板.hpp | 1.03 KB | 2018-08-31 |
二分查找模板.hpp | 0.98 KB | 2018-08-31 |
快速幂.hpp | 0.42 KB | 2018-08-31 |
排序-堆排序.hpp | 1.02 KB | 2018-08-31 |
排序-归并排序.hpp | 0.20 KB | 2018-08-31 |
排序-快速排序.hpp | 0.88 KB | 2018-08-31 |
排序-桶排序.hpp | 0.68 KB | 2018-08-31 |
发表评论 取消回复