package com.example.medium;

/**
 * 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.
 * @author FuPing
 *
 */
public class SearchMatrix {
    /**
     * 二维空间的折半查找
     * 改进建议:确定列的范围时，需要比较相邻的两个值，此时可以一次移动两个，来加快收敛速度
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null)return false;
        int row = matrix.length;
        if(row == 0)return false;
        if(matrix[0] == null)return false;
        int column = matrix[0].length;
        if(column == 0)return false;
        if(target < matrix[0][0] && target > matrix[row - 1][column - 1])return false;
        int cIndex = 0;
        int head = 0,tail = row - 1,middle = 0;
        while(head <= tail){//确定行数
            middle = (head + tail)/2;
            if(matrix[middle][0] == target){
                return true;
            }else if(matrix[middle][0] > target){//middle行最小值大于目标值
                if(middle > 0 && matrix[middle - 1][0] <= target){
                    middle--;
                    break;
                }
                tail = middle - 1;
            }else{//middle行最小值小于目标值
                if(middle < row - 1 && matrix[middle + 1][0] > target){
                    break;
                }
                head = middle + 1;
            }
        }
        if(target >= matrix[middle][0] && target <= matrix[middle][column - 1]){//目标值存在于当前行
            cIndex = middle;
            head = 0;
            tail = column - 1;
            while(head <= tail){//行中折半查找
                middle = (head + tail)/2;
                if(matrix[cIndex][middle] == target){
                    return true;
                }else if(matrix[cIndex][middle] > target){
                    tail = middle - 1;
                }else{
                    head = middle + 1;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        long startTime = System.currentTimeMillis();
        int matrix[][] = {{1,   3,  5,  7},{10, 11, 16, 20},{23, 30, 34, 50},{57, 60, 75, 80},{85, 90, 95, 98}};
        System.out.println(new SearchMatrix().searchMatrix(matrix, 60));
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间:"+(endTime-startTime) + "ms");

    }

}