前提: 已排序
時(shí)間復(fù)雜度: O(logN)
例如: 找出某個(gè)target出現(xiàn)的位置（隨機(jī)），某個(gè)target第一次出現(xiàn)的位置，某個(gè)target最后一次出現(xiàn)的位置
問題: 如果在未排序的數(shù)組中使用二分搜索，結(jié)果會(huì)怎么樣？
答: 如果二分搜索聲稱找到了target，那么該target就一定存在于數(shù)組中，
但是，在應(yīng)用于未排序數(shù)組時(shí)，算法有時(shí)會(huì)在target實(shí)際存在的情況下報(bào)告說該target不存在
代碼:
int
vector_bsearch(struct Vector *vector, const void *target, compare_func compare)
{
int lo, hi, mid, tmp;
lo = 0;
hi = (vector->count) - 1;
while(lo <= hi) {
mid = lo + ((hi - lo) >> 1);
tmp = compare(vector->array[mid], target);
if(tmp == 0)
return mid;
else if(tmp > 0)
hi = mid - 1;
else
lo = mid + 1;
}
return -1;
}
int
vector_lower(struct Vector *vector, const void *target, compare_func compare)
{
int lo, hi, mid;
lo = -1;
hi = vector->count;
/* distance between lo and hi at least larger than 1, which ensure mid won't equals to either lo or hi */
while(lo+1 != hi) {
/* loop invariant: vector[lo]<target && vector[hi]>=target && lo<hi */
mid = lo + ((hi - lo) >> 1);
if(compare(vector->array[mid], target) >= 0)
hi = mid;
else
lo = mid;
}
if(hi>=(vector->count) || compare(vector->array[hi], target)!=0)
return -1;
return hi;
}
int
vector_upper(struct Vector *vector, const void *target, compare_func compare)
{
int lo, hi, mid;
lo = -1;
hi = vector->count;
/* distance between lo and hi at least larger than 1, which ensure mid won't equals to either lo or hi */
while(lo+1 != hi) {
/* loop invariant: vector[lo]<=target && vector[hi]>target && lo<hi */
mid = lo + ((hi - lo) >> 1);
if(compare(vector->array[mid], target) <= 0)
lo = mid;
else
hi = mid;
}
if(lo<0 || compare(vector->array[lo], target)!=0)
return -1;
return lo;
}