Data Structure: Set

Lecture notes for MIT6.006 Lec8 Set and Sorting.

In this Lecture, we will implement a simple interface, set.

Set Interface

Remember Data Structure is an interface, don’t do some dumb jobs… All you need to do is understanding the first principle of several data structures through practicing it.

If you use simply an array, it will cost $O(n)$ time！

Data Structure Set

Lecture Notes from SJTU DS

集合的定义

集合包含两个部分：键值和关键字值。

静态查找表

问题的定义：给定一个集合，需要查找关键字$X$对应的元素是否存在。

从最基本的顺序查找（$O(n)$）到对于有序集合的二分查找($O(\log n)$），还可以进一步优化为插值查找，对于数据均匀分布的情况，可以进一步优化时间复杂度：

$$pos = low + \left\lfloor \frac{(high - low) \cdot (target - arr[low])}{arr[high] - arr[low]} \right\rfloor$$

使用分块查找也可以进一步优化（详见分块思想）

STL 中的静态查找表

• find()：

  • 模版参数
    • 迭代器类型
    • 集合元素的类型
  • 形式参数
    • 两个迭代器对象（左闭右开）
    • 需要查找的对象值
  • 返回一个迭代器

• binary_search()：使用二分查找的方式查找一个有序序列，返回是否存在