正确的代码可以写做如下:
int bs(int *a, int b, int e, int v) { int *begin = a + b, int *end = a + e, *mid; if (!a || b >= e) return -1; while (begin < end) { mid = begin + ((end - begin) >> 1); if (*mid > v) end = mid; else if (*mid < v) begin = mid + 1; else return mid - a; } return -1; }
如果是把最后一行代码return -1变成
return mid - a;
那么如果这个数不在这个数组中的情况下,那么返回的这个位置刚好是比这个数小,或者比这个数大。如果需要刚好<=的数。那么
int bs(int *a, int b, int e, int v) { int *begin = a + b, int *end = a + e, *mid; if (!a || b >= e) return -1; while (begin < end) { mid = begin + ((end - begin) >> 1); if (*mid > v) end = mid; else if (*mid < v) begin = mid + 1; else return mid - a; } while (*mid > v) --mid; return mid - a; }
则可以得到那个刚好比其小的数。