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

O(logN * M)

每一个数组用二分查找，然后结合得到

数组查找用二分，左右指针分别指向首末元素，且左闭右闭（循环不变量很重要）

public class Solution {
public boolean Find(int target, int [][] array) {
    boolean bool = false;
    for(int [] nums : array){
        bool = bool | find(target, nums);
    }
        
    return bool;
}

public boolean find(int target, int[] nums){
    int left = 0;
    int right = nums.length - 1;//左闭右闭
    while(left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] == target) return true;
        else if(nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}
}

O(N + M)

用两个指针分别指向，左下和右上，且左闭右闭（循环不变量很重要）

左下的指针只能向上向右

右上的指针只能向下向左

且每次一定走一步，因为有两个指针，所以最多走（n + m）/ 2步数

此题，指针指向左上和右下，不可取，因为一次判断之后，有两种走法，都不能排除

public class Solution {
public boolean Find(int target, int [][] array) {//O(N++M)
    int left_r = array.length - 1;//向上向右
    int left_c = 0;
    int right_r = 0;//向下向左
    int right_c = array[0].length - 1;
    
    while(left_r >= right_r && left_c <= right_c){
        if(array[left_r][left_c] == target) return true;
        else if(array[left_r][left_c] < target) left_c ++;
        else left_r --;
        
        if(array[right_r][right_c] == target) return true;
        else if(array[right_r][right_c] < target) right_r ++;
        else right_c --;
    }
    return false;
}
}