离散化算法的二分法应用

我们思考一个问题：其实这里的二分法回归本源也是基于下标映射的原理，只是实现是借助二分的形式。

在排序好的数组中对目标数值进行二分搜索，在 O(logn) 的时间复杂度内找到该数值是整体数据中的第几个。

具体的我们可以如下操作：

• 数值 10 ---> 二分搜索 10 ---> 有序序列中第 4 位置
• 数值 3 ---> 二分搜索 3 ---> 有序序列中第 0 位置
• 数值 8 ---> 二分搜索 8 ---> 有序序列中第 9 位置
• 数值 9 ---> 二分搜索 9 ---> 有序序列中第 3 位置
• 数值 4 ---> 二分搜索 4 ---> 有序序列中第 1 位置

复杂度

时间复杂度： O(logn)
主要体现在排序中，其余操作  <= O(logn)

空间复杂度： O(n)
主要体现在用于排序的辅助数组中
不考虑 sort 中使用的空间

代码

对下方代码的注释：

1. 以 C++ 描述
2. 以整形数据 int 描述
3. 默认数据无重复值
4. 接口名见下

/*** @param odata 原始数据* @param start 起始数值 (一般为0/1)* @return std::vector<int> 经过离散化后的data*/
vector<int> discrete(const vector<int>& odata, int start = 0) ;

 好了，今天的文章分享就到这里了，希望对大家的学习有帮助哦！