二分题目模版式题解

前言

前文 二分搜索 中介绍了二分搜索的原理和模版，但是本人感觉并不是很完美。大量刷题的积累，发现了一个很不错的模版，传送门 👉 二分查找算法模板

本篇文章以「二分」为专题，罗列了高频重要的相关题目，而且本文所有题目的代码思路严格保持一致，也就是遵循传送门中通用的算法模版！！

题目

704. 二分查找

public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (nums[m] >= target) r = m;
        else l = m + 1;
    }
    return nums[l] == target ? l : -1;
}

69. x 的平方根

xxxxxxxxxx
public int mySqrt(int x) {
    if (x == 0) return 0;
    int l = 1, r = x;
    while (l < r) {
        int m = l + r + 1 >>> 1;
        if (x / m >= m) l = m;
        else r = m - 1;
    }
    return l;
}

374. 猜数字大小

xxxxxxxxxx
public int guessNumber(int n) {
    int l = 1, r = n;
    while (l < r) {
        int m = l + r + 1 >>> 1;
        if (guess(m) >= 0) l = m;
        else r = m - 1;
    }
    return l;
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

xxxxxxxxxx
public int missingNumber(int[] nums) {
    int l = 0, r = nums.length;
    while (l < r) {
        int m = l + r >>> 1;
        if (nums[m] > m) r = m;
        else l = m + 1;
    }
    return l;
}

33. 搜索旋转排序数组

xxxxxxxxxx
public int search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r + 1 >> 1;
        if (nums[m] <= nums[r]) {
            if (nums[m] <= target && target <= nums[r]) l = m;
            else r = m - 1;
        } else {
            if (nums[l] <= target && target <= nums[m]) r = m;
            else l = m + 1;
        }
    }
    return nums[l] == target ? l : -1;
}

153. 寻找旋转排序数组中的最小值

xxxxxxxxxx
public int findMin(int[] nums) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (nums[m] <= nums[r]) r = m;
        else l = m + 1;
    }
    return nums[l];
}

154. 寻找旋转排序数组中的最小值 II

xxxxxxxxxx
public int findMin(int[] nums) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (nums[m] == nums[r]) r--;
        else if (nums[m] < nums[r]) r = m;
        else l = m + 1;
    }
    return nums[l];
}

81. 搜索旋转排序数组 II

xxxxxxxxxx
public boolean search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r + 1 >> 1;
        if (nums[m] == target) return true;
        if (nums[m] == nums[r]) r--;
        else if (nums[m] < nums[r]) {
            if (nums[m] <= target && target <= nums[r]) l = m;
            else r = m - 1;
        } else {
            if (nums[l] <= target && target <= nums[m]) r = m;
            else l = m + 1;
        }
    }
    return nums[l] == target;
}

278. 第一个错误的版本

xxxxxxxxxx
public int firstBadVersion(int n) {
    int l = 1, r = n;
    while (l < r) {
        int m = l + r >>> 1;
        if (isBadVersion(m)) r = m;
        else l = m + 1;
    }
    return l;
}

162. 寻找峰值

xxxxxxxxxx
public int findPeakElement(int[] nums) {
    int n = nums.length, l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (m + 1 < n && nums[m] > nums[m + 1]) r = m;
        else l = m + 1; 
    }
    return l;
}

34. 在排序数组中查找元素的第一个和最后一个位置

xxxxxxxxxx
public int[] searchRange(int[] nums, int target) {
    int n = nums.length;
    if (n == 0) return new int[]{-1, -1};
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (target <= nums[mid]) r = mid;
        else l = mid + 1;
    }
    int r1 = nums[l] == target ? l : -1;
    l = 0; r = n - 1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (target >= nums[mid]) l = mid;
        else r = mid - 1;
    }
    int r2 = nums[l] == target ? l : -1;
    return new int[]{r1, r2};
}

35. 搜索插入位置

xxxxxxxxxx
public int searchInsert(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (target <= nums[mid]) r = mid;
        else l = mid + 1;
    }
    return nums[l] >= target ? l : l + 1;
}

74. 搜索二维矩阵

xxxxxxxxxx
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int l = 0, r = m * n - 1;
    while (l < r) {
        int mid = l + r >> 1;
        int row = mid / n, col = mid % n;
        if (target <= matrix[row][col]) r = mid;
        else l = mid + 1;
    }
    return matrix[l / n][l % n] == target;
}

658. 找到 K 个最接近的元素

​x
public List<Integer> findClosestElements(int[] arr, int k, int x) {
    int n = arr.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (arr[m] >= x) r = m;
        else l = m + 1;
    }
    int left = l - 1, right = r + 1;
    if (l > 0 && arr[l] != x) {
        int t = x - arr[l - 1] <= arr[l] - x ? l - 1 : l;
        left = t - 1; right = t + 1;
    }

    while (right - left - 1 < k) {
        if (left >= 0 && right < n) {
            if (x - arr[left] <= arr[right] - x) left--;
            else right++;
        } else if (left >= 0) left--;
        else if (right < n) right++;
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = left + 1; i < right; i++) ans.add(arr[i]);
    return ans;
}

29. 两数相除

xxxxxxxxxx
public int divide(int dividend, int divisor) {
    if (dividend == 0) return 0;
    if (divisor == 1) return dividend;
    if (divisor == -1) {
        if (dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE;
        return -dividend;
    }
    long a = dividend, b = divisor;
    if ((a > 0 && b > 0) || (a < 0 && b < 0)) return (int) f(Math.abs(a), Math.abs(b));
    return (int) f(Math.abs(a), Math.abs(b)) * -1;
}
private long f(long a, long b) {
    if (a < b) return 0L;
    long res = 1, t = b;
    while (t + t <= a) {
        res += res;
        t += t;
    }
    return res + f(a - t, b);
}

875. 爱吃香蕉的珂珂

xxxxxxxxxx
public int minEatingSpeed(int[] piles, int h) {
    int l = 1, r = (int) 1e9;
    while (l < r) {
        int v = l + r >> 1;
        if (check(piles, h, v)) r = v;
        else l = v + 1;
    }
    return l;
}
private boolean check(int[] piles, int h, int v) {
    int cnt = 0;
    for (int x : piles) {
        cnt += (x + v - 1) / v;
    }
    return cnt <= h;
}

668. 乘法表中第k小的数

xxxxxxxxxx
public int findKthNumber(int m, int n, int k) {
    if (m > n) return findKthNumber(n, m, k);
    int l = 0, r = (int) 1e9;
    while (l < r) {
        int v = l + r >> 1;
        if (check(m, n, k, v)) r = v;
        else l = v + 1;
    }
    return l;
}
private boolean check(int m, int n, int k, int v) {
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        cnt += Math.min(n, v / i);
    }
    return cnt >= k;
}

436. 寻找右区间

xxxxxxxxxx
public int[] findRightInterval(int[][] intervals) {
    int n = intervals.length;
    Integer[] idx = IntStream.range(0, n).boxed().toArray(Integer[]::new);
    Arrays.sort(idx, (a, b) -> intervals[a][0] - intervals[b][0]);
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    for (int i = 0; i < n; i++) {
        int l = i, r = n - 1, target = intervals[idx[i]][1];
        while (l < r) {
            int m = l + r >> 1;
            if (target <= intervals[idx[m]][0]) r = m;
            else l = m + 1;
        }
        if (l < n && target <= intervals[idx[l]][0]) ans[idx[i]] = idx[l];
    }
    return ans;
}

528. 按权重随机选择

xxxxxxxxxx
class Solution {

    private int n;
    private int[] ps;
    private Random random = new Random();

    public Solution(int[] w) {
        n = w.length;
        ps = new int[n + 1];
        for (int i = 0; i < n; i++) ps[i + 1] = ps[i] + w[i];
    }
    
    public int pickIndex() {
        int target = random.nextInt(ps[n]) + 1;
        int l = 1, r = n;
        while (l < r) {
            int m = l + r >> 1;
            if (ps[m] >= target) r = m;
            else l = m + 1;
        }
        return l - 1;
    }
}

497. 非重叠矩形中的随机点

xxxxxxxxxx
class Solution {

    private int n;
    private int[] ps;
    private int[][] rs;
    private Random random = new Random();

    public Solution(int[][] rects) {
        n = rects.length;
        rs = rects;
        ps = new int[n + 1];
        for (int i = 0; i < n; i++) {
            ps[i + 1] = ps[i] + (rs[i][2] - rs[i][0] + 1) * (rs[i][3] - rs[i][1] + 1);
        }
    }
    
    public int[] pick() {
        int target = random.nextInt(ps[n]) + 1;
        int l = 1, r = n;
        while (l < r) {
            int m = l + r >> 1;
            if (ps[m] >= target) r = m;
            else l = m + 1;
        }
        int x = rs[l - 1][0] + random.nextInt(rs[l - 1][2] - rs[l - 1][0] + 1);
        int y = rs[l - 1][1] + random.nextInt(rs[l - 1][3] - rs[l - 1][1] + 1);
        return new int[]{x, y};
    }
}

240. 搜索二维矩阵 II

xxxxxxxxxx
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int i = m - 1, j = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] == target) return true;
        if (matrix[i][j] < target) j++;
        else i--;
    }
    return false;
}