題目

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]
]

思路

我這裡提供了3個解法

1.解法一就是一個一個搞，大家都會的

2.解法二就是先找每一行的最後一個數字，因為這個2維數組是一個有序的，所以通過判斷每一行的最後一個數字可以知道我們要比較的數字在不在當前行

步驟： 一。如果在這一行，那麼從這一行的最後一列往前面移動，如果遍歷過了該行的所有列，而且沒有找到，那麼最後的結果就是沒有找到

二。如果不在這一行，那麼移動到下一行，然後在比較。

3.解法三就是用二分法來做。把2維數組看成是一維數組。

代碼

解法一就不弄了，直接從解法二開始

解法二：

    

public class Solution {  
        public boolean searchMatrix(int[][] matrix, int target) {  
            int row = 0;  
            int col = matrix[0].length-1;  
            for(;row< matrix.length&&col>=0;)  
            {  
                if(matrix[row][col] == target)  
                    return true;  
                else if ( matrix[row][col] < target)  
                {  
                    row++;  
                }  
                else  
                {   
                            col--;  
                }  
            }  
              
            return false;  
        }  
}

解法三：

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
		int row = matrix.length;
		int col = matrix[0].length;
		int end = row * col -1;
		
		int begin = 0;
		while( begin <= end )
		{
			int middle = ( end +begin )/2;
			
			if( matrix[middle/col][middle%col] == target)
			{
				return true;
			}
			else if (matrix[middle/col][middle%col] < target)
			{
				begin = (middle/col)*col+middle%col+1;
			}
			else
			{
				end = (middle/col)*col+middle%col-1;
			}
		}
		
		return false;
    }
}