代码

int binary_search(const unsigned *a, int n, unsigned x)
{
	int l = 0, r = n - 1, mid;
    if (r - l > 200) {
        mid = l + (r - l) * (x - a[l]) / (a[r] - a[l]);
        while (l < r - 200) {
            if (x > a[mid]) l = mid;
            else r = mid;
            mid = l + (r - l) * (x - a[l]) / (a[r] - a[l]);
        }
    }
    else mid = (l + r) / 2;
    
    while (l < r - 1) {
        if (x > a[mid]) l = mid;
        else r = mid;
        mid = (l + r) / 2;
    }
    if (x > a[mid]) {
        while (mid < n) {
            if (x > a[mid]) mid++;
        }
        return mid;
    }
    else {
        if (x == a[mid]) return mid;
        while (mid >= 0) {
            if (x < a[mid]) mid--;
        }
        return mid;
    }
}

评测结果