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

有序二维数组对应元素查找

方法1 暴力求解法
用for循环对二维数组进行遍历，找出对应目标元素
时间复杂度 O(n*2)
空间复杂度 O(1)

public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[0].length;j++){
                if(array[i][j] == target){
                    return true;
                }
            }
        }
        return false;
    }
}

方法2 固定开始元素
由于二维数组是有序排列，故可以先固定左下角或右上角元素，通过移动来查找目标元素
注：二维数组中每行的元素空位是一样的，所以更方便移动
时间复杂度 O(行高+列高)
空间复杂度 O(1)

public class Solution {
    public boolean Find(int target, int [][] array) {
        int len = array.length;
        int wid = array[0].length;
        if(len<=0 || wid<=0){
            return false;
        }
        int len0 = len-1;
        int wid0 = 0;
        while(len0>0 && wid0<wid-1){
            if(array[len0][wid0] < target)
                wid0++;
            if(array[len0][wid0] > target)
                len0--;
            if(array[len0][wid0] == target)
                return true;
        }
        return false;
    }
}

方法3 二分法查找
对于有序数组的查找，通常采用二分法进行遍历,这里对每一行采用二分查找法
时间复杂度 O(mlog(n))
空间复杂度O(1)

public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0; i<array.length; i++){
            int low = 0;
            int hign = array[0].length-1;
            int mid = (low + hign) / 2;
            while(low<=hign){
                if(array[i][mid]<target){
                    low = mid+1;
                }
                if(array[i][mid]>target){
                    hign = mid-1;
                }
                if(array[i][mid]==target){
                    return true;
                }
                mid = (low + hign) /2;
            }
        }
        return false;
    }
}