二分

数组二分

二分的思想很简单，但真实现起来坑很多。记录一个模版，足够应付大部分二分场景。

求满足条件的最左位置

int binarySearch(int[] a, int n, int key) {
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + (r - l ) / 2; // 向下去整，二分点偏左
        if (a[m] < key) { // 先算左区间，判断范围不包含返回条件，这里就是不能包含a[m]==key
            l = m + 1; // m不在返回条件范围内，l自然不能取
        } else {
            r = m;
        }
    }
    if (a[l] == key) {
        return l;
    }
    return -1;
}

求满足条件的最右位置

int binarySearch(int[] a, int n, int key) {
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + (r + 1 - l ) / 2; // 向上去整，二分点偏右
        if (a[m] > key) { // 先算右区间，判断范围不包含返回条件，这里就是不能包含a[m]==key
            r = m - 1; // m不在返回条件范围内，r自然不能取
        } else {
            l = m;
        }
    }
    if (a[l] == key) {
        return l;
    }
    return -1;
}