Leetcode: Search a 2D Matrix

1 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
 2 
 3 Integers in each row are sorted from left to right.
 4 The first integer of each row is greater than the last integer of the previous row.
 5 For example,
 6 
 7 Consider the following matrix:
 8 
 9 [
10   [1,   3,  5,  7],
11   [10, 11, 16, 20],
12   [23, 30, 34, 50]
13 ]
14 Given target = 3, return true.      

這道題本來思路并不複雜，先對第一列做binary search, 找到target所在的行，再對所在的行做binary search，找到target在或不在。但是我在程式設計的時候遇到了很多問題，堆棧溢出（StackOverflowError）折騰死我了，一些邊界條件的考慮也頗費周折。

我之是以會碰到堆棧溢出的問題是跟我用recursion的方法來做binary search分不開的。衆所周知，recursion的一大缺陷就是，浪費空間，容易遞歸太深造成堆棧的溢出。在這道題中可見一斑。其實它的sample input: [[1][3]], 3 遞歸的層次并不多，但是我要用recursion就不得不把整個矩陣作為recursion function的參數，結果雖然層次不多但是堆棧依然溢出了。後來想想那不是當然的麼，每一層堆棧都要存下整個矩陣，不溢出才怪。是以，我就把方法改成了iteration, 果然就避免了堆棧溢出的問題。由此可見，recursion雖然好想，但是需要很大空間的缺點不容忽視。以後如果我發現有可能遞歸太深或者每一次遞歸的參數需要的空間很大，我就應該避免使用遞歸的方法。

後面我還寫了一個程式驗證我的想法，我在對找到的行做binary search的時候用遞歸，不過這一次我用的參數不再是一整個矩陣，而是矩陣的這一行。結果，這次堆棧沒有溢出。accept了。這證明了我之前的想法，果然用一個矩陣做遞歸參數真是太天真了。教訓啊，我太naive了。不過，人不是就這樣一點一點經驗積攢而進步的嗎？

1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         if(matrix==null || matrix.length==0 || matrix[0].length==0) 
 6             return false;
 7         int start = 0, end = matrix.length*matrix[0].length-1;
 8         
 9         while(start<=end){
10             int mid=(start+end)/2, midX=mid/matrix[0].length,
11                 midY=mid%matrix[0].length;
12             if(matrix[midX][midY]==target) return true;
13             if(matrix[midX][midY]<target){
14                 start=mid+1;
15             }else{
16                 end=mid-1;
17             }
18         }
19         return false;
20     }
21 }