算法效率

Question

假如有一堆数字(升序)，如1，3，8，11，29....想从中找到某个数字（如10），如果10存在则返回10，而此时10并不存在，那么则返回比10大或小的第一个数（此时应该是8或者11） 该如何设计算法？

Answer 1

数字没规律，线性查找吧...返回<n的时候注意第一个>n，返回>n时注意最后一个<n

Answer 2

int BinarySearch(int* a, const int& x, int& left, int& right)
{
while(left <= right)
{
int middle = (left + right) / 2;
if(x == a[middle])
return middle;
if(x > a[middle])
left = middle + 1;
else
right = middle - 1;
}
return -1;
}
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
int a[] = {1, 3, 8, 11, 29};
const int key = 10;
int left = 0;
int right = sizeof(a)/sizeof(a[0])-1;
int nIndex = BinarySearch(a, key, left, right);
if(-1 != nIndex)
printf("index: %d\n", nIndex);
else
{
printf("> %d : %d\n", key, a[left]);
printf("< %d : %d\n", key, a[right]);
}
return 0;
}

Answer 3

LZ这个问题说真的，大2就该知道怎么做了。lower_bound应该能满足你的需求。

Answer 4

lower_bound的查找方式是否适合大数据量的查找呢？貌似lower_bound使用的是遍历方式？？？

Answer 5

首先已排序，数据范围不确定，最好的方式就是二分查找了。至于什么堆，BST解决此类问题不太有效。
堆首先要建堆(nlogn)，然后不断pop前k个极值，调整堆(klogn),对于找前k个最大数据比较有效(stl里make_heap...)。
BST和二分类似，不过要保持平衡，代码麻烦点。
lower_bound是顺序遍历还是什么的，看看源码就知道了，大多数常用自己写的话，很可能不如STL的算法实现，效率、可扩展性这些难以达到STL的高度。

Answer 6

万分感谢！我看了源码，用的是二分查找，所以看来lower_bound就应该是我的选择了！谢谢。