二分查找（折半查找）
二分查找：利用表的有序性排除待查找元素中的一半
牢记：
• 二分查找只能发生在有序数组上
• 时间复杂度为O(lgn)
• 二分查找每次排除一半，至多log2(n) + 1次后结束 => 复杂度为O(lg(n))
二叉查找树
• 二叉查找树中任意结点：>左子树所有结点，<右子树所有结点
哈希表（散列表）
建立 元素值->数组下标 的映射（哈希），直接判断目标值是否存在结构中（哈希表）
例：元素为{22，6，19，18，2}，通过 h(x) = x % 7（哈希函数） 的映射关系将其映射到数组对应位置上
哈希表冲突
就是你想插入元素进哈希表里时候已经有其他的元素了。
解决办法1：开放地址法😀
仍旧是这个表
现在插入元素29, 哈希值为1，产生了冲突
继续下一级哈希：
h1 = (29 + 1) % 7
解决办法2：链地址法
仍然冲突？再哈希：
h2 = (29 + 2) % 7
29经过3次哈希，放入了nums[3]
将哈希值相同的元素存放在 同一个单链表 中
h(x) = x % 7，依次插入22，6，19，18，2，29，30，42，10，54，50
哈希函数是一个映射：元素值 -> 哈希值
不同的元素拥有相同的哈希值：冲突
哈希函数应尽量能较为均匀地映射元素 => 降低冲突概率
京公网安备 11010502036488号