NC29 矩阵查找 算法java实现

题目描述

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
例如：
对于下面的矩阵：
[
[1, 3, 5, 9],
[10, 11, 12, 30],
[230, 300, 350, 500]
]
要搜索的目标值为3，返回true；
示例1
输入：[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],3
返回值：true

解题思路

遇到找数字，而且是有序的数组里面找数字，第一想到的就是二分法查找法，这里由于是二维数组，因此需要先定位找到数字所在的那行，然后再在那行中寻找是否有数字。

测试用例

[[1]],2
[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],1
[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],301
[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],500

代码实现

import java.util.*;


public class Solution {
    /**
     * 测试用例：
      
[[1,3,5,9]],2

[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],1
[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],301
[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],500


     * @param matrix int整型二维数组 
     * @param target int整型 
     * @return bool布尔型
     */
    public boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        int left=0;
        int right=matrix.length-1;
        int middle=0;
        int row=0;
        //先找到数字所在的
        while(left<=right){
            middle=(right-left)/2+left;
            if(matrix[middle][0]>target){
                right=middle-1;
            }else if(matrix[middle][matrix[0].length-1]<target){
                left=middle+1;
            }else{  
                row=middle;
                break;
            }
        }
        
        left=0;
        right=matrix[0].length-1;
        middle=0;
        while(left<=right){
            middle=(right-left)/2+left;
            if(matrix[row][middle]>target){
                right=middle-1;
            }else if(matrix[row][middle]<target){
                left=middle+1;
            }else{    
                return true;
            }
        }
        
        return false;
    }
}