前提: 已排序
时间复杂度: 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;
}