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. 总结
- 循环条件都是
l < r getL和lower_bound是一样的，除了最后的判断 l 是不是目标值getR和upper_bound的区别在于left = mid+1还是让right=mid-1
-
- 如果是获取
= x的最右边的位置，那么当x<a[mid]的时候，说明目标位置还在左边的区间，right=mid-1 - 如果是获取
>x的最左边的位置，那么当x<a[mid]的时候，说明 mid 的大小不够，需要向右移动，此时 mid 位置的值不需要考虑，left = mid+1
- 如果是获取
- “最左”判定条件都是
<=
