我的编程珠玑

未分类

关于二分查找的返回下标 i，可以理解为被查找元素 val 需要插入（有序数组）的位置。
若干样例：
+ a = [1, 2, 3, 4, 5]; val = 2; return i = 1;
+ a = [1, 3, 4, 5, 6]; val = 2; return i = 1;
+ a = [1, 2, 3, 4, 5]; val = 0; return i = 0;
+ a = [1, 2, 3, 4, 5]; val = 6; return i = 5;
所有的下标均是从 0 开始计数

int binary_search(int* a, int begin, int end, int val) {
    int i, j, mid;
    i = begin;
    j = end;
    while (i <= j) {
        mid = i + (j - i) / 2;
        if (val == a[mid]) {
            return mid;
        } else if (val < a[mid]) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    return i;
}