第74题：搜索二维矩阵

一． 问题描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:

matrix = [

  [1,   3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 50]

]

target = 3

输出: true

示例 2:

输入:

matrix = [

  [1,   3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 50]

]

target = 13

输出: false

二． 解题思路

解题思路：采用二分查找的方法进行查找

步骤一：首先对第一列进行二分查找，找到目标数可能在哪一行。

步骤二：对目标行进行二分查找，判断目标数是否存在(这一题步骤二偷懒了，直接遍历的)。

三． 执行结果

执行用时 :1 ms, 在所有 java 提交中击败了78.93%的用户

内存消耗 :42.7 MB, 在所有 java 提交中击败了38.63%的用户

四． Java代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix==null||matrix.length<=0||matrix[0].length<=0)
        {
            return false;
        }
     int row=0;
     int first=0;
     int second=matrix.length-1;
     
     
     while(first<=second)
     {
         row=(first+second)/2;
         if((row<matrix.length-1&&(matrix[row][0]<=target&&matrix[row+1][0]>target))||((row==matrix.length-1)&&(matrix[row][0]<=target))){
           break;
         }
         else 
         {
             if(matrix[row][0]>target)
             {
                 second=row-1;
             }
             else 
             {
                 first=row+1;
             }
         }
     }
     
    
     for(int i=0;i<matrix[row].length;i++)
     {
         if(matrix[row][i]==target)
         {
             return true;
         }
     }
     return false;
    }
}