题解 | 二维数组中的查找

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param array int整型二维数组 
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        // write code here
        // 时间复杂度O(n * m)，待优化
        // 数组为空直接返回false
        if(array == null || array.length == 0 || array[0].length == 0){
            return false;
        }
        // target小于最小元素或者大于最大元素，也可以直接返回false
        if(array[0][0] > target || array[array.length - 1][array[0].length - 1] < target){
            return false;
        }

        int line = 0, lineEnd = array.length - 1;
        // 遍历数组行
        while(line <= lineEnd){
            int rowLeft = 0, rowRight = array[0].length - 1;
            // 遍历某行里的所有元素
            while(rowLeft < rowRight){
                // 或者本行最中间元素的值，判断方式和一维数组一样
                int mid = (rowLeft + rowRight) / 2;
                int curVal = array[line][mid];
                if(curVal == target){
                    return true;
                } else if (curVal > target){
                    rowRight = mid;
                } else {
                    rowLeft = mid;
                }

                if(rowRight - rowLeft == 1){
                    if(array[line][rowLeft] == target || array[line][rowRight] == target){
                        return true;
                    }
                    break;
                }
            }
            // 判断下一行
            line++;
        }

        // 如果没找到则默认返回false
        return false;
    }
}