二分

前言

仅看要点不是很能理解，主要是看示例

要点总结复习用

要点

1. 关注范围，需要的是\([left,right]\)还是\([left,right)\)
2. 定义最后 \(l\) 和 \(r\) 落点位置是什么
3. 根据落点，描述循环不变式，即 \(l\) 的左边恒为 什么， \(r\) 的右边恒为 什么

例子

LowerBound

在 求非严格递增序列中，求第一个大于等于 \(value\) 的数的下标

定义循环结束后 \(l\) 落在第一个大于等于 \(value\) 的数的位置，则循环不变量为：

1. \(R\) 的右边（不含\(R\)）一定是大于等于 \(value\) 的
2. \(L\) 的左边（不含\(L\)）一定是小于 \(value\) 的

若定义左闭右闭区间

// left 落在第一个大于等于 value 的数的位置
public static int lowerbound(int[] arr, int left, int right, int value) {
    //左闭右闭
    //如arr下标从0~n-1，则left=0，right=n-1
    //如果区间不为空
    while (left <= right) {
        int mid = left + right >> 1;
        //mid位置的数小于value，则[left,mid]一定都是小于value的，根据循环不变量 L左边一定是小于value的
        //又由于区间是左闭的，所以left指向mid + 1
        if (arr[mid] < value) left = mid + 1;
        //否则mid位置的数大于等于value，则[mid+1,right]都是大于等于value的，根据循环不变量 R右边一定是大于等于value的
        //又由于是右闭的，所以right指向mid - 1
        else right = mid - 1;
    }
    return left;
}

若定义左闭右开区间

// left 落在第一个大于等于 value 的数的位置
public static int lowerbound(int[] arr, int left, int right, int value) {
    //左闭右开
    //如arr下标从0~n-1，则left=0，right=n
    //如果区间不为空
    while (left < right) {
        int mid = left + right >> 1;
        //mid位置的数小于value，则[left,mid]一定都是小于value的，根据循环不变量 L左边一定是小于value的
        //又由于区间是左闭的，所以left指向mid+1
        if (arr[mid] < value) left = mid+1;
        //否则mid位置的数大于等于value，则[mid+1,right)都是大于等于value的，根据循环不变量 R右边一定是大于等于value的
        //又由于是右开的，所以right指向mid
        else right = mid;
    }
    return left;
}

UpperBound

在 求非严格递增序列中，求第一个大于 \(value\) 的数的下标

定义循环结束后 \(l\) 落在第一个大于 \(value\) 的数的位置，则循环不变量为：

1. \(R\) 的右边（不含\(R\)）一定是大于 \(value\) 的
2. \(L\) 的左边（不含\(L\)）一定是小于等于 \(value\) 的

若定义左闭右闭区间

// left 落在第一个大于 value 的数的位置
public static int upperbound(int[] arr, int left, int right, int value) {
    //左闭右闭
    //如arr下标从0~n-1，则left=0，right=n-1
    //如果区间不为空
    while (left <= right) {
        int mid = left + right >> 1;
        //mid位置的数小于等于value，则[left,mid]都是小于等于 value 的
        //根据循环不变量，left左边都是小于等于value的
        //左闭区间，left指向mid+1
        if (arr[mid] <= value) left = mid + 1;
        //否则mid位置的数大于value，则[mid,right]都是大于 value 的
        //根据循环不变量，right右边都是大于 value 的
        //右闭区间，right指向mid-1
        else right = mid - 1;
    }
    return left;
}

若定义左闭又开区间

// left 落在第一个大于 value 的数的位置
public static int upperbound(int[] arr, int left, int right, int value) {
    //左闭右开
    //如arr下标从0~n-1，则left=0，right=n
    //如果区间不为空
    while (left < right) {
        int mid = left + right >> 1;
        //mid位置的数小于等于value，则[left,mid]都是小于等于 value 的
        //根据循环不变量，left左边都是小于等于value的
        //左闭区间，left指向mid+1
        if (arr[mid] <= value) left = mid + 1;
        //否则mid位置的数大于value，则[mid,right)都是大于 value 的
        //根据循环不变量，right右边都是大于 value 的
        //右开区间，right指向mid
        else right = mid;
    }
    return left;
}