接到一个优化算法任务
数据库储存着银行卡号用上下限表示的区间，互不交叉重叠，现有9万多记录。给一个卡号，如何找到该条记录。现有方法是使用前三位数做索引字段，起到一定效果，但是数据一大了还是效率低。我推测了一下其应用情景是银行每个网点所具有的发卡权不一样，某个区间属于某个网点所发。阶段一、IP反查城市既然不是一下子能想到答案的，我首先想到的是，是否已有解决方案。我想到了一个类似但普遍的应用情景：ip反查城市于是谷歌关键字搜索。http://www.haogongju.net/art/2459667http://bbs.csdn.net/topics/80467465http://coolshell.cn/articles/7048.html自己知乎提问http://www.zhihu.com/question/25024287
阶段二、区间hash 区间搜索仔细查hash，认识了gperf这个生成完美hash函数的gnu工具。二维数组的现有hash成果，geohash地图算法http://www.cnblogs.com/LBSer/p/3310455.html相较于Peano曲线而言，Hilbert曲线没有较大的突变http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html针对一群范围对的最快查找算法设计（不要用数组）？其实我一直在考虑能不能用哈希来做，也就是每个区间一个hash值，每个数一个hash值，两者对应起来进行查找，这样就是O(1)的速度了，但想了想作罢了，因为：1. 这样的哈希算法能找到吗？比如两个区间：<1, 3>, <9, 11>，能让1,2,3都对应一个哈希值，然后9, 10, 11都对应一个哈希值，还要与对应的区间对应一个哈希值，这样的哈希算法目前没想到。2. 因为我的算法必须是没有误报率的，因此怕hash的做法会引来冲突和误报率二分查找直接就搞定了，并且复杂度是下界。。。因为区间是静态的，并且不相交（条件太强了），也没有什么动态更新的操作，线段树、树状数组RMQ神马的根本没有发挥的空间。。。即使可以动态加减区间，只要满足不相交，用个二叉查找树就好了，也不需要线段树。
大型路由器为了速度，貌似对这种查找的速度做过大量优化，用的比较多的
lz不一定非的信赖stl。这是我以前自己实现的一个map测试10个区间，Release，优化全开MaxSpeed，10W次查找，耗时2.7秒http://www.cnblogs.com/huangxincheng/archive/2012/07/21/2602375.html哈希适合等于性的查找，树结构适合”范围查找“，lucene适合字符串的查找
今天成果1、logN是查找的下限了。最好方法是读到内存，用二叉查找数，或者二分查找下限数组。2、除非真找到那个hash函数，使得区间与区间内的任意值都具有相同hash值。用反证法应该容易证明不可能吧！