LeetCode-74-Search a 2D Matrix

Search a 2D Matrix

 

来自 <https://leetcode.com/problems/search-a-2d-matrix/>

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.

题目解读

写一个能够从m x n 的矩阵中找出特定值的高校算法，这个矩阵有以下特点

• 每一行的整数从左到右为有序的
• 每一行的第一个数比上一行的最后一个数大。

例如

 

考虑如下矩阵

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

给定target=3, 返回true.

 

解析一：

最直接的方法就是从前往后，从左到右进行遍历整个数组，时间复杂度为O(mn).

 

解析二：

由于给定的矩阵从左到右，从上到下都是有序的，所以可以首先考虑到二分查找，首先找到target大致在哪一行，然后找出其确定位置。

 

解析一代码（略）

 

 

解法二代码

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int low = 0;
		int high = matrix.length-1;
		int mid = (low + high) / 2;
		
		/**
		 * 二分查找target大致在哪一行
		 */
		while(low<=high) {
			mid = (low + high) / 2;
			if( matrix[mid][0] == target)
				return true;
			else if (matrix[mid][0] < target)
				low = mid+1;
			else
				high = mid-1;
		}
		
		//target所在的行是low和high中小的那个
		int row = (low+high) / 2;
		low = 0;
		high = matrix[mid].length-1;
		
		/**
		 * 二分查找target所在的具体位置
		 */
		while(low<=high) {
			mid = (low + high) / 2;
			if( matrix[row][mid] == target)
				return true;
			else if (matrix[row][mid] < target)
				low = mid+1;
			else
				high = mid-1;
		}
		return false;
    }
}

解法二性能