[cpp]
//
/*
二分查找是基於排好序的算法。復雜度低,並且很高效,
由於項目中大量使用的了二分查找,但是又不能每個業務實現一個
因此有必要實現一個通用的二分查找
其主要思想:通過對已經排好序的數組,進行數據指針的比較。
@const void *key 需要查找的key值
@const void *base, 所要查找數據的首地址
@int nmemb,所要查找的成員數量
@int size, 每個元素的大小
@int *piEqual,是否能查找到的標志查到為1,否則為0
*/
int bsearch_int (const void *key, const void *base, int nmemb, int size, int *piEqual)
{
size_t l, u, idx;
const void *p, *p2;
int comparison, comparison2;
*piEqual = 0;
if (nmemb < 0) return -1;
if (!nmemb) return 0;
l = 0;
u = nmemb;
while (l < u)
{
idx = (l + u) / 2;
p = (void *) (((const char *) base) + (idx * size));
comparison = *(int *)key - *(int *)p ;
if (comparison == 0)
{
*piEqual = 1;
return idx;
}
else if (comparison < 0)
{
if (idx == 0) return idx;
p2 = (void *) (((const char *) base) + ((idx - 1) * size));
comparison2 = *(int *)key - *(int *)p2 ;
if (comparison2 > 0) return idx;
u = idx;
}
else /*if (comparison > 0)*/
{
l = idx + 1;
}
}
return u;
}