bsearch

stl版本:

int t = bsearch(a, a+n, x) - a;

while (l < r) {
    int mid = l + r >> 1;
    if (x < a[mid]) r = mid; 
    else l = mid + 1;
}

或者

while (l < r) {
    int mid = l + r + 1 >> 1;
    if (x < a[mid]) r = mid - 1;
    else l = mid;
}

lower_bound(x)

stl版本

int t = lower_bound(a, a+n, x) - a;

int mid = l + r >> 1;

[l, mid] [mid+1, r]

若 x <= mid; r = mid;
若 x > mid; l = mid + 1;

if (a[r] < x) return r + 1; // 如果不存在，就返回next available position

while (l < r) {
    int mid  = l + r >> 1;
    if (x <= mid) r = mid;
    else l = mid+1;
}
return r;

upper_bound(x)

stl版本

int t = upper_bound(a, a+n, x) - a;

int mid = l + r >> 1;

[l, mid] [mid+1, r]

若 x < mid; r = mid;
若 x >= mid; l = mid + 1;

if (a[r] < x) return r+1; // 如果不存在，就返回next available position

while (l < r) {
    int mid =  l + r >> 1;
    if (x < mid) r = mid;
    else l = mid + 1;
}

return r;

qsort

stl版本

sort(a, a+n);
stable_sort(a, a+n);

void qsort(int a[], int l, int r) {
    int x = a[l + r >> 1];
    int i = l-1, j = r+1;
    while (i < j) {
        while (a[++i] <= x);
        while (a[--j] >= x); // 由于j在后面移动，所以后面也是用j
        if (i < j) swap(a[i], a[j]);
    }
    qsort(a, l, j);
    qsort(a, j+1, r);
}