线性表取范围算法

Question

各位大虾，现在遇到一个算法，现在有一个顺序的线性表a[n],现在给出一个数值，怎么快速的求出这个值在表中的那个区间啊~~比如  a[0]=1,a[2]=4,a[3]=7,a[4]=13,给出一个数，比如5，怎样快速求出它是在a[2]与a[3]之间，效率最好是O(1).谢谢啦~~~

Answer 1

         那就快速排序呗

Answer 2

O(1)恐怕做不到吧...除非你这个线性表里面的数据是有规律的,并且你有这些数据的生成函数.
这样以来,你找到逆函数,用哈希的思想能做到O(1).否则的话,二分恐怕是最快的了...

Answer 3

悲剧啊，除了二分法和开数组空间换时间之外有没有牛人能想到更好的算法啊？

Answer 4

折半查找或者索引查找都可以很快的定位数据，但时间复杂度肯定大于O(1)。