// all i < lo, arr[i] < x
int bisect_left(int arr, int x){
int lo = 0, hi = arr.length, mid;
while (lo < hi):
mid = (lo+hi) / 2;
if (a[mid] < x) lo = mid+1;
else hi = mid;
return lo;
}
Bisect_right
// all i >= lo, arr[i] > x
int bisect_left(int arr, int x){
int lo = 0, hi = arr.length, mid;
while (lo < hi):
mid = (lo+hi) / 2;
if (a[mid] > x) hi = mid;
else lo = mid + 1;
return lo;
}