二分查找的边界问题

我们都知道对于一个单调数组，对其进行二分查找的复杂度一般为O(log N)
通过控制上下界lo和hi不断缩小范围得到

二分查找模版

普通二分查找（找到目标target即可）

public class BinarySearch {
    public int search(int[] arr, int target){
        int lo = 0, hi = arr.length - 1;
        while(lo <= hi){
            int mid = lo + (hi - lo) / 2;       //为了防止 (hi + lo) / 2 发生整型溢出
            if(target > arr[mid]) lo = mid + 1;
            else if(target < arr[mid]) hi = mid - 1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-1, 0, 3, 5, 9, 12};
        System.out.println(new BinarySearch().search(arr, 9));
    }
}

其中查找区间为[lo, hi]，即左闭右闭，因此while循环内条件为lo <= hi

1. 当查询到mid所在下标值为target时停止
2. 若mid所在下表值小于target，则说明目标值在当前区间右半侧，故将闭区间左端点调整为mid + 1
   
3. 若mid所在下表值大于target，则说明目标值在当前区间左半侧，故将闭区间左端点调整为mid - 1
   

二分查找下界

例如数组{1, 2, 2, 2, 2, 3, 4, 5}
当查找2时，区间缩小时可能取到下标1, 2, 3, 4任意一点，故需要重新修改边界条件
代码如下:

public class BinarySearch {
    public int search(int[] arr, int target){
        int res = -1;
        int lo = 0, hi = arr.length - 1;
        while(lo <= hi){
            int mid = lo + (hi - lo) / 2;
            if(target > arr[mid]) lo = mid + 1;
            else {
                if(arr[mid] == target) res = mid;   //若满足要求提前将res记录
                hi = mid - 1;   //排除当前mid，继续缩小区间
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 2, 2, 3, 3, 5};
        System.out.println(new BinarySearch().search(arr, 5));
    }
}

若$arr[mid] \leq target$

• 若小于，则应该缩小上界，继续向下搜索
• 若等于，则应该首先标记当前mid下标为res，再排除当前mid以后的所有元素，继续尝试向下查找

二分查找上界

同理，与上方类似
二分下界查找如下：

public class BinarySearch {
    public int search(int[] arr, int target){
        int res = -1;
        int lo = 0, hi = arr.length - 1;
        while(lo <= hi){
            int mid = lo + (hi - lo) / 2;
            if(target < arr[mid]) hi = mid - 1;
            else {
                if(arr[mid] == target) res = mid;
                lo = mid + 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 2, 2, 3, 3, 5};
        System.out.println(new BinarySearch().search(arr, 3));
    }
}

二分查找例题

leetcode 1870. 准时到达的列车最小时速 Round 242 T2

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 $10^7$ ，且 hour 的 小数点后最多存在两位数字 。

示例 1：
输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：
第 1 趟列车运行需要 1/1 = 1 小时。
由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
你将会恰好在第 6 小时到达。

示例 2：
输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：
第 1 趟列车运行需要 1/3 = 0.33333 小时。
由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
你将会在第 2.66667 小时到达。

示例 3：
输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。

提示：

• n == dist.length
• 1 <= n <= 10^5
• 1 <= dist[i] <= 10^5
• 1 <= hour <= 10^9
• hours 中，小数点后最多存在两位数字

我们可以用二分的方法寻找到能够按时到达的最小时速。
由于时速必须为正整数，因此二分的下界为 $1$；对于二分的上界，我们考虑 $hours$ 为两位小数，因此对于最后一段路程，最小的时限为 $0.01$，那么最高的时速要求即为 $dist[i] / 0.01 \leq 10^7$ ，同时为二分时速的上界, 即$dist \leq 10^9$。注意向上取整细节

class Solution {
public static int minSpeedOnTime(int[] dist, double hour) {
        if ((((dist[dist.length - 1] * 1.0) / (10000000 * 1.0)) + dist.length - 1) > hour) {
            return -1;
        }
        int left = 1;
        int right = 1000000000;
        int speed = left + (right - left) / 2;
        int result = -1;
        while (left < right) {
            boolean isOk = judge(speed, dist, hour);
            if (isOk) {
                result = result == -1 ? speed : Math.min(result, speed);
                right = speed;
            } else {
                left = speed + 1;
            }
            speed = left + (right - left) / 2;
        }
        if (result != -1) {
            return result;
        }
        boolean isOk = judge(speed, dist, hour);
        if (isOk) {
            return speed;
        } else {
            return -1;
        }
    }
    private static boolean judge(int speed, int[] dist, double hour) {
        double time = 0.0;
        for (int i = 0; i < dist.length - 1; i++) {
            time += ceilDiv(dist[i], speed);
            if (time > hour) {
                continue;
            }
        }
        time += (dist[dist.length - 1] * 1.0) / (speed * 1.0);
        return time <= hour;
    }
    private static int ceilDiv(int a, int b) {
        int temp = Math.floorDiv(a, b);
        if (temp * b < a) {
            return (temp + 1);
        } else {
            return temp;
        }
    }
}

leetcode 962. 最大宽度坡

给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] < A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。

示例 1：
输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

示例 2：
输入：[9,8,1,0,1,9,4,0,4,1]
输出：7
解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.

维护一个max数组，自右向左遍历当前最大元素
再A数组自左向右一次遍历，查询max数组中大于A[i]的元素下标的上界，查询后将差与res取大

class Solution {
    public int maxWidthRamp(int[] A) {
        int len = A.length;
        int[] max = new int[len];
        int tmp = 0;
        int res = 0;
        for(int i = len - 1; i >= 0; i--){
            tmp = Math.max(tmp, A[i]);
            max[i] = tmp;
        }
        //System.out.println(Arrays.toString(max));
        for(int i = 0 ; i < len; i++){
            int target = search(max, i + 1, A[i]);
            //System.out.println(i + " " + target);
            if(target != -1) res = Math.max(res, target - i);
        }
        return res;
    }
    public int search(int[] arr, int start, int target){
        int lo = start, hi = arr.length - 1;
        int ans = -1;
        while(lo <= hi){
            int mid = lo + (hi - lo) / 2;
            //System.out.println(lo + " " + hi + " " + mid);
            if(arr[mid] < target){
                hi = mid - 1;
            }
            else{
                ans = mid;
                lo = mid + 1;
            }
        }
        return ans;
    }
}

leetcode 4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• $-10^6$ <= nums1[i], nums2[i] <= $10^6$

mid表示arr1左侧的元素数量

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if(len1 < len2) return solve(nums2, nums1);
        else return solve(nums1, nums2);
    }
    public double solve(int[] arr1, int[] arr2){
        int len1 = arr1.length;
        int len2 = arr2.length;
        int n = len1 + len2;
        int half = n / 2;
        int lo = half - len2, hi = half;
        int mid = 0, low_b = 0, a1lmax = 0, a1rmin = 0, a2lmax = 0, a2rmin = 0;
        while(lo <= hi){
            mid = lo + (hi - lo) / 2;
            low_b = half - mid;
            a2lmax = (low_b == 0? Integer.MIN_VALUE: arr2[low_b - 1]);
            a2rmin = (low_b == len2? Integer.MAX_VALUE: arr2[low_b]);
            a1rmin = (mid == len1? Integer.MAX_VALUE: arr1[mid]);
            a1lmax = (mid == 0? Integer.MIN_VALUE: arr1[mid - 1]);
            if(a1rmin < a2lmax){
                lo = mid + 1;
            }
            else if(a2rmin < a1lmax){
                hi = mid - 1;
            }
            else break;
        }
        //System.out.println(mid);
        //System.out.println(a1lmax + " " + a1rmin);
        //System.out.println(a2lmax + " " + a2rmin);
        if(n % 2 == 1) return (double)Math.min(a2rmin, a1rmin);
        else return (Math.max(a1lmax , a2lmax) + Math.min(a2rmin, a1rmin)) / 2.0;
    }
}