查找算法(折半查找，二叉排序树，哈希表/散列查找)

折半查找

1. 把low放在最左边，high放最右边，mid=(high+low)/2
2. 如果low<=high则循环，当待查找数<mid，则high=mid-1，当待查数>mid，则low+1

3. 当low=mid的时候，该值与查找数相等，则输出，否则当循环结束后仍未找到则break

   时间复杂度O(log2n)，比较次数<=树的深度=log2n

   顺序储存有序表

分块查找

• 块间有序，块内无序
• 因此块间可以用折半查找法确定在哪一个块，再用顺序查找一个个看在块中哪个位置

二叉排序树

• if左子树不空，则左子树均小于根结点，if右子树不空，则右子树均大于根结点。具有递归性质，中序遍历则可得有序序列。

  

• 二叉排序树的创建和插入都是按照上面查找的原则。新插入的结点一定的新的叶子结点
• 创建二叉排序树时间复杂度为O(nlog2n)，插入一个的时间复杂度为O(log2n)
• 删除:删去叶子节点无影响; 只有左子树或右子树，用左孩或右孩填补; 若左右都不为空，则找直接前驱或直接后继补。

  

  散列表(哈希表)
• 思想: 通过对元素关键字的运算，直接求出元素的地址
• 散列函数两个原则: 函数简单，每个关键字只有一个对应; 分布均匀，少冲突
• 构造地址函数方法:

1. 数学分析法: 取中间几位乱序的数 ，或加减乘除等作为地址(首先要知道每一位数的分布情况)
2. 平方取中法: 先把编码平方后，取中间的几位数
3. 折叠法: 按n个数为间隔隔开，再加起来。

4. 除留余数法: 选择适当的p值(一般选小于表长的最大质数)，对关键字取余(最好)

   以上方法可以自由组合

• 处理冲突方法

1. 开放地址法: H=(H(key)+d)%表长。d可以以线性序列(1，2，3…表长-1)，可以是二次探测(1²，-1²，2²，-2²…(表长/2)²)，也可以是随机数。只要发生冲突的地址，则进行下一次探测
2. 链地址法: 把相同地址的记录放在同一个单链表中。该适用于表长不确定的情况