查找篇
查找方法
二分查找
通过(high+lo)>>>1不断下分直到找到数据
迭代:
时间复杂度为O(n)
二叉排序树
哈希
O(1)
插值查找
对二分查找的进化,就能选择更好的范围开始检索,而不是上来就直接折半。
让mid值可以更加贴近target
int mid = lo+(target-a[lo])/(a[hi]-a[lo])*(hi-lo)
斐波那契查找
同样是对二分查找的优化,前后两数的比例趋近于0.618
红黑树等等
跳跃表
又称为skip-list
简单来说,每一个节点不单止包括下一个结点的指针,同时可能包含多个指向后续结点的指点,这样就可以跳过不必要的结点,加快查找、删除等操作。对于一个节点有多少个指向下个节点的指针由random函数控制