/**

 * Created by lvhao on 2017/8/1.

 *

 Write an efficient algorithm that searches for a value in an m x n matrix.

 This matrix has the following properties:

 Integers in each row are sorted from left to right.

 The first integer of each row is greater than the last integer of the previous row.

 For example,

 Consider the following matrix:

 [

 [1,   3,  5,  7],

 [10, 11, 16, 20],

 [23, 30, 34, 50]

 ]

 Given target = 3, return true.

 */

/*

* 思路是先找到target所在的行，然后在这一行找有没有，找寻的方式都是二分查找*/

public class Q74Searcha2DMatrix {

    public boolean searchMatrix(int[][] matrix, int target) {

        if (matrix.length == 0 || matrix[0].length == 0)

            return false;

        int sta = 0;

        int fin = matrix.length,mid=0;

        boolean res = false;

        //二分法查找行

        while(sta < fin)

        {

            mid = (sta + fin)/2;

            if (matrix[mid][0] <= target)

            {

                //如果这一行开头小于等于target且下一行开头大于它（或这一行就是最后一行）

                if ((mid + 1) >= matrix.length || matrix[mid+1][0] > target)

                    break;

                else

                    sta++;

            }

            else

            {

                fin--;

            }

        }

        int row = mid;

        sta = 0;

        fin = matrix[0].length;

        //二分法查找数据

        while (sta < fin)

        {

            mid = (sta + fin)/2;

            if (matrix[row][mid] == target)

            {

                res = true;

                break;

            }

            else if (matrix[row][mid] > target)

            {

                fin--;

            }

            else

            {

                sta++;

            }

        }

        return res;

    }

}