upper bound and lower bound
int bs_upper_bound(int *a, int n, int x) { int l = 0; int h = n; while (l < h) { int mid = (l + h) / 2; if (x >= a[mid]) { l = mid + 1; } else { h = mid; } } return l; } int bs_lower_bound(int *a, int n, int x) { int l = 0; int h = n; while (l < h) { int mid = (l + h) / 2; if (x <= a[mid]) { h = mid; } else { l = mid + 1; } } return l; }