#74

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

在一個2D matrix中找某integer是否存在。

Concept find out target belongs to which row, then use binary search 看每個row的最後一個element，若比target大，則target可能在該row。

Implementation 找到row後，要在那個row裡binary search， 此時有出一點小問題： 一開始我將l和r都設成mid，r 發現當target不存在row中時，會無法跑出迴圈， l和r會是相鄰的兩個element。 最後改成l = mid+1, r = mid-2就好了。

Code

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        /*
        find out target belongs to which row, then use binary search
        */

        int m = matrix.length;
        if(m==0)    return false;
        int n = matrix[0].length;
        if(n==0)    return false;

        int row = 0;
        if(matrix[m-1][n-1] < target)
            return false;
        while(matrix[row][n-1] < target && row < m){
            row++;
        }

        int l=0, r=n;
        while(l <= r){
            int mid = (l+r)/2;
            //if((r-l)==1 && target > matrix[row][l] && target < matrix[row][r])
            //    break;
            if(matrix[row][mid] < target){
                l = mid+1;
            }else if(matrix[row][mid] > target){
                r = mid-1;
            }else{
                return true;
            }
        }
        /*for(int i=0; i<n; i++){
            if(target == matrix[row][i])
                return true;
        }*/

        return false;
    }
}