package lms.algorithm.refers2offer.array;

/**

 * <功能简述>在一个二维数组中（每个一维数组的长度相同），

 * 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

 *

 */

public class TwoDimensionFind {

    public static boolean findInArray(int target, int[][] array) {

        //对每行数组 二分法

        //for循环 每层循环代表数组每行

        for (int m = 0; m < array.length; m++) {

            //每行中利用二分法进行查找

            int start = 0, end = array[m].length - 1;

            while (start <= end) {

                int mid = (start + end) / 2;

                if (target > array[m][mid]) {

                    start = mid + 1;

                } else if (target < array[m][mid]) {

                    end = mid - 1;

                } else {

                    return true;

                }

            }

        }

        return false;

    }

    public static void main(String[] args) {

        int[][] arr = {{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{5,6,7,8,9}};

        boolean flag = findInArray(9,arr);

        System.out.println(flag);

    }

}