二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

分析题目

题目属于二维数组,采用两层for循环遍历每一个元素可以判断出是否含有该整数，时间复杂度 O($n^2$)

根据题目的特点数据每行每列递增;因此可以采用二分法，先确定数据在哪一行，然后再采用二分法确定数据在哪一列，从而确定具体有没有这个数。时间复杂度O(n+nlog(n))

解决办法

1. 暴力法

public boolean Find(int target, int [][] array) {
    boolean result = false;
    int width = array[0].length; //数组宽度 （列数）
    int height = array.length;  // 数组高度 （行数）
    for(int i=0;i<height;i++){
        for(int j =0;j<width;j++){
            if(target == array[i][j]){
                result = true;
                    break;
            }
        }
    }
return result;
}

2. 二分法

public class Solution {
    public boolean Find(int target, int [][] array) {
          
        boolean result = false;
        int width = array[0].length; //数组宽度 （列数）
        if(width == 0){
            // 空二维数组
            return false;
        }
        for (int[] ints : array) {
            if (ints[0] <= target && ints[width - 1] >= target) {
                //数据在第i行
                /// 2.再确定再哪一列(在这一行内二分查找)
                int minIndex = 0;
                int maxIndex = width-1;
                while (maxIndex - minIndex > 1) {
                    int middle = (int) Math.floor((minIndex + maxIndex) / 2.0);
                    if (target > ints[middle]) {
                        minIndex = middle;
                    } else {
                        maxIndex = middle;
                    }
                    if (target == ints[middle] || target == ints[minIndex]||target==ints[maxIndex]) {
                        result = true;
                        break;
                    }
                }
            }
        }
        return result;
    }
}