【算法】二分

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. “最左”判定条件都是 <=

原文地址：https://blog.csdn.net/leadera_/article/details/143822624

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！