【算法】二分

1. 找到有序区间中 =x 最左边的数字的位置

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

2. 找到有序区间中 =x 最右边的数字的位置

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

r = mid - 1;和int mid = l + r + 1 >> 1;的操作是绑定的

3. 找到有序区间中 >=x 第一个数字的位置

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

4. 找到有序区间中 >x 第一个数字的位置

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

5. 总结

1. 循环条件都是 l < r
2. getL和lower_bound是一样的，除了最后的判断 l 是不是目标值
3. getR和upper_bound的区别在于left = mid+1 还是让right=mid-1

1. 1. 如果是获取= x 的最右边的位置，那么当 x<a[mid] 的时候，说明目标位置还在左边的区间，right=mid-1
   2. 如果是获取>x 的最左边的位置，那么当 x<a[mid] 的时候，说明 mid 的大小不够，需要向右移动，此时 mid 位置的值不需要考虑，left = mid+1

1. “最左”判定条件都是 <=