题解 | #二维数组中的查找#

同240. 搜索二维矩阵 II,C++版本看这里题解 | #二维数组中的查找#

public class Solution {
    int target, m, n;
    public boolean Find(int target, int[][] array) {
        this.m = array.length;// m行
        if (m == 0) return false;
        this.n = array[0].length;// n 列
        this.target = target;
        return reduceFullSearch(array);
        //return lineSearch(array);
        //return binarySearch(array);
        //return twoWayBinarySearch(array, 0, n, 0, m);
        //return twoWayBinarySearch1(array, 0, n - 1, 0, m - 1);
    }

        private boolean reduceFullSearch(int[][] array){
        int flag=n;//用来缩进
        for(int i=0;i<m;i++){
            for(int j=0;j<flag;j++){//标准两个for
                if(target==array[i][j]){
                    return true;
                }
                if(target<array[i][j]){
                    flag=j;
                }//下一行缩进
            }//forj end
        }//fori end
        return false;
    }

    /**
     * 线性搜索 O(M+N) O(1)
     *
     * @param array
     * @return
     */
    private boolean lineSearch(int[][] array) {
        // 左下角起
        int l = 0, d = m - 1;
        // 往右上角搜索
        while (l < n && d >= 0) {
            if (array[d][l] == target) {
                return true;
            } else if (array[d][l] > target) {
                --d;
            } else {
                ++l;
            }
        }
        return false;
    }


    /**
     * 二分搜索 O(M*log(N)) O(1)
     *
     * @param array 矩阵数组
     * @return
     */
    private boolean binarySearch(int[][] array) {
        for (int i = 0; i < m; i++) {
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (array[i][mid] == target) {
                    return true;
                } else if (array[i][mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }// while end
        }// fori end
        return false;
    }


    /**
     * 双向二分搜索 分冶 O(log(M)*log(N)) O(1)
     * right down 取不到
     *
     * @param array 矩阵数组
     * @param left  矩阵 左边界
     * @param right 矩阵 右边界 取不到
     * @param up    矩阵 上边界
     * @param down  矩阵 下边界 取不到
     * @return
     */
    private boolean twoWayBinarySearch(int[][] array, int left, int right, int up, int down) {
        //System.out.println("left="+left+"right="+right+"up="+up+"down="+down);
        // right > left down > up
        if (left >= right || up >= down) {
            return false;
        }
        int midY = (left + right) / 2;
        int midX = (up + down) / 2;
        int midPivot = array[midX][midY];
        if (midPivot == target) {
            return true;
        } else if (midPivot > target) {
            return twoWayBinarySearch(array, left, midY, up, down) || twoWayBinarySearch(array, left, right, up, midX);
        } else {
            return twoWayBinarySearch(array, midY + 1, right, up, down) || twoWayBinarySearch(array, left, right, midX + 1, down);
        }
    }

    /**
     * 双向二分搜索 分冶 O(log(M)*log(N)) O(1)
     * right down 可以取到
     *
     * @param array 矩阵数组
     * @param left  矩阵 左边界
     * @param right 矩阵 右边界
     * @param up    矩阵 上边界
     * @param down  矩阵 下边界
     * @return
     */
    private boolean twoWayBinarySearch1(int[][] array, int left, int right, int up, int down) {
        //System.out.println("left="+left+"right="+right+"up="+up+"down="+down);
        // right >= left down >= up
        if (left > right || up > down) {
            return false;
        }
        int midY = (left + right) / 2;
        int midX = (up + down) / 2;
        int midPivot = array[midX][midY];
        if (midPivot == target) {
            return true;
        } else if (midPivot > target) {
            return twoWayBinarySearch1(array, left, midY - 1, up, down) || twoWayBinarySearch1(array, left, right, up, midX - 1);
        } else {
            return twoWayBinarySearch1(array, midY + 1, right, up, down) || twoWayBinarySearch1(array, left, right, midX + 1, down);
        }
    }
}