Leetcode74. 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.

题目含义：

给定一个有序的二维数组，其中每一行的最后一个元素，比下一行的第一个元素都要大，，要求我们在这个二维数组中寻找指定的元素。

解题思路：

我们可以将这个二维数组看成一个整体有序的一维数组，因此相当于一个一维有序数组中寻找指定元素，也可以分别根据列和行使用两次二分法，寻找目标元素。

具体实现：

public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) { return false; } if (matrix[0] == null || matrix[0].length == 0) { return false; } int row = matrix.length; int column = matrix[0].length; //在行中寻找最后一个小于目标元素的行 int start = 0; int end = row - 1; while (start + 1 < end) { int mid = start + (end - start)/2; if (matrix[mid][0] == target) { return true; } else if (matrix[mid][0] < target) { start = mid; } else { end = mid; } } if (matrix[end][0] <= target) { row = end; } else if (matrix[start][0] <= target) { row = start; } else { return false; } //寻找在某一行中是否存在目标元素。 start = 0; end = column - 1; while (start + 1 < end) { int mid = start + (end - start)/2; if (matrix[row][mid] == target) { return true; } else if (matrix[row][mid] < target) { start = mid; } else { end = mid; } } if (matrix[row][start] == target) { return true; } else if (matrix[row][end] == target) { return true; } else { return false; } } }

这里只是实现分别对行和列进行两次二分查找。