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

//方法一：暴力解法，两层遍历矩阵。时间复杂度为：O(n^m)
//方法二：二分法，两层遍历矩阵。时间复杂度为：O(n*logm)
public class Solution {
    public boolean Find(int target, int [][] array) {
//         //方法一：暴力解法，两层遍历矩阵。时间复杂度为：O(n^m)
//         int length = array.length;//一维数组长度
//         //空数组处理
//         if(length == 0){
//             return false;
//         }
//         int len = array[0].length;//二维数组长度
//         //遍历
//         for(int i=0;i<length;i++){
//             for(int j=0;j<len;j++){
//                 if(array[i][j] == target){
//                     return true;
//                 }
//             }
//         }

//         return false;
        
        //方法二：二分法，两层遍历矩阵。时间复杂度为：O(n*logm)
        int length = array.length;//一维数组长度
        //空数组处理
        if(length == 0){
            return false;
        }
        for(int i=0;i<length;i++){//将每一维数组都使用二分法查找
            if(find(target,array,i)){
                return true;
            }
        }
        
        return false;
    }
    
    public boolean find(int target,int[][] array,int i){
        int len = array[i].length;
        //特殊值处理
        if(len == 0){
            return false;
        }
        int min = 0;//最小值索引
        int max = len-1;//最大值索引
        int mid = (min+max)/2;//中值索引
        while(min<=max){//循环结束条件
            if(array[i][mid] == target){//找到目标值
                return true;
            }else if(array[i][mid] > target){//中值大于目标值，目标值在左区间
                max = mid - 1;//更新最大值
            }else{//中值小于目标值，目标值在右区间
                min = mid + 1;//更新最小值
            }
            mid = (min+max)/2;//更新中值
        }
        if(min>max){//判断退出while循环的方式，一是return终止循环，二是条件不满足是退出循环
            return false;
        }
        
        return true;//没有意义的返回值
    }
}