对半检索

对半检索，又称对分检索、折半查找，是一种在很多对象中快速定位一个对象的数学方法。集合中的每个对象被分配给一个键。而键的数量总是2的次方，多出来的键将作为虚构键存在。在执行查找的时候，对象的键会按照表格的形式列出来，欲查找的对象会和列表的中点值对比，如果欲查找对象的键值比中点值小，那么键值小于中点值的对象都被保留，剩下的则被抛弃。反之，键值大于中点值得对象被保留，剩下的被抛弃。整个查找过程会不断重复，直到列表中只剩下一个对象，也就是欲查找的对象。