前提: 已排序
時間復雜度: O(logN)
例如: 找出某個target出現的位置（隨機），某個target第一次出現的位置，某個target最后一次出現的位置
問題: 如果在未排序的數組中使用二分搜索，結果會怎么樣？
答: 如果二分搜索聲稱找到了target，那么該target就一定存在于數組中，
但是，在應用于未排序數組時，算法有時會在target實際存在的情況下報告說該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;
}