面试算法笔记

求大于 目标值 v(>0) 的最小值,精确到 3 位小数 */ double min_bigger(double v) { // 初始化上下界 double lo = v - EPSILON, hi = INF; for (size_t i = 0; i < 100; i++) { // 100 次循环已经能达到相当的精度 double mid = lo + (hi - lo) / 2.0; if (mid

应用介绍

二分查找模板

注意点:

    - 是否存在重复元素

模板 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

}

。。。。。。。。想了解详情请下载附件。

文件列表(部分)

名称 大小 修改日期
Algorithm_for_Interview.vcxproj2.88 KB2018-08-31
Algorithm_for_Interview.vcxproj.filters2.43 KB2018-08-31
all.h0.44 KB2018-08-31
main.cpp0.41 KB2018-08-31
test.hpp0.18 KB2018-08-31
Cpp之STL容器.md4.30 KB2018-08-31
Cpp之string专题.hpp1.42 KB2018-08-31
Cpp之常用方法.md2.42 KB2020-09-08
IO模板.hpp1.33 KB2018-08-31
README.md0.38 KB2018-08-31
heap.hpp0.89 KB2018-08-31
list.hpp0.77 KB2018-08-31
map.hpp1.14 KB2018-08-31
queue.hpp0.61 KB2018-08-31
set.hpp1.32 KB2018-08-31
stack.hpp0.43 KB2018-08-31
vector.hpp1.13 KB2018-08-31
不通过继承实现多态.hpp0.80 KB2018-08-31
位运算.hpp0.84 KB2018-08-31
遍历所有子集.hpp0.71 KB2018-08-31
遍历所有正因子.hpp0.48 KB2018-08-31
atoi.hpp0.99 KB2018-08-31
dp-01背包.hpp0.21 KB2018-08-31
二分查找最优解模板.hpp1.03 KB2018-08-31
二分查找模板.hpp0.98 KB2018-08-31
快速幂.hpp0.42 KB2018-08-31
排序-堆排序.hpp1.02 KB2018-08-31
排序-归并排序.hpp0.20 KB2018-08-31
排序-快速排序.hpp0.88 KB2018-08-31
排序-桶排序.hpp0.68 KB2018-08-31

立即下载

相关下载

[面试算法笔记] 求大于 目标值 v(>0) 的最小值,精确到 3 位小数 */ double min_bigger(double v) { // 初始化上下界 double lo = v - EPSILON, hi = INF; for (size_t i = 0; i < 100; i++) { // 100 次循环已经能达到相当的精度 double mid = lo + (hi - lo) / 2.0; if (mid

评论列表 共有 0 条评论

暂无评论

微信捐赠

微信扫一扫体验

立即
上传
发表
评论
返回
顶部