搜索二维矩阵[二分巧用 + 记录不同于插入二分的解法]

前言

有序数组或其他，就应该紧密联系二分法。但二分法有很多细节，主要分为二分查找/二分插入寻位置。而今天刷到了该题，需求不同于二分插入寻找位置，它要寻找比target刚刚小的位置，而不是后一个。

一、搜索二维矩阵

二、记录不同于插入二分的解法

package everyday.medium;

// 搜索二维矩阵
public class SearchMatrix {
    
    /* target：快速搜索矩阵中是否存在目标值。 矩阵每行都有一个特点，那就是有序，而且列也有序，但这个序不真实。把矩阵看成一位矩阵(平铺)，答案即晓。 所以行列两次二分即可。 */
    public boolean searchMatrix(int[][] matrix, int target) {
    
        // bug1:先列再行，应该先行再列。
        // 二分找target 在第几行。
        int low = 0, high = matrix.length - 1;
        while (low < high) {
    
            // 这里是值得记录的地方
            // 不同于插入二分，这里找的是刚好比这个数大的位置，而不是后一个位置。
            // 处理方式也很简单，int mid = low + (high - low + 1 >>> 1); 配合 else low = mid;
            int mid = low + (high - low + 1 >>> 1);
            int midVal = matrix[mid][0];
            if (midVal > target) high = mid - 1;
            else low = mid;
        }
        // 找target 在第几列。
        int col = binarySearch(matrix[low], target);

        return matrix[low][col] == target;
    }

    private int binarySearch(int[] nums, int target) {
    
        int low = 0, high = nums.length - 1;
        while (low < high) {
    
            // 取上，区别于平时的升序插入，这里要找刚好比自己小的位置。
            int mid = low + (high - low + 1 >>> 1);
            int midVal = nums[mid];
            if (midVal > target) high = mid - 1;
            else low = mid;
        }
        return low;
    }
}

总结

1）有序与二分的紧密相连，要在头脑中紧密联系。
2）不同于插入二分的解法。

参考文献

[1] LeetCode 搜索二维矩阵