1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 16, 2015
4+ Problem: Search a 2D Matrix
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/search-a-2d-matrix/
7+ Notes:
8+ Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
9+
10+ Integers in each row are sorted from left to right.
11+ The first integer of each row is greater than the last integer of the previous row.
12+ For example,
13+
14+ Consider the following matrix:
15+
16+ [
17+ [1, 3, 5, 7],
18+ [10, 11, 16, 20],
19+ [23, 30, 34, 50]
20+ ]
21+ Given target = 3, return true.
22+
23+ Solution: Binary-search.
24+ */
25+ public class Solution {
26+ public boolean searchMatrix (int [][]matrix ,int target ) {
27+ if (matrix .length ==0 ||matrix [0 ].length ==0 )return false ;
28+ int N =matrix .length ,M =matrix [0 ].length ;
29+ int left =0 ,right =M *N -1 ;
30+ while (left <=right ) {
31+ int mid =left + (right -left ) /2 ;
32+ int row =mid /M ,col =mid %M ;
33+ if (matrix [row ][col ] ==target )return true ;
34+ if (matrix [row ][col ] <target )left =mid +1 ;
35+ else right =mid -1 ;
36+ }
37+ return false ;
38+ }
39+ }
