74. Search a 2D Matrix

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

/*
74. Search a 2D Matrix 
Total Accepted: 74543 Total Submissions: 222239 Difficulty: Medium
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.

Hide Tags Array Binary Search
Hide Similar Problems (M) Search a 2D Matrix II
*/
import java.util.*;

public class SearchMatrix {
    public static void main(String[] args) {
        int[][] matrix1 = { {1,   3,  5,  7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
        int[][] matrix2 =  {{1}, {3}};
        int[][] matrix3 = {{-5}};
        int target = 3;
    
        System.out.println(searchMatrix(matrix1, target) == true ?
            " Test case 1 success" : " Test case 1 failed");
        System.out.println(searchMatrix(matrix2, target) == true ?
            " Test case 2 success" : " Test case 2 failed");
        System.out.println(searchMatrix(matrix3, target) == false ? 
            " Test case 3 success" : " Test case 3 failed");
    }
	
    public static boolean searchMatrix(int[][] matrix, int target) {
        /*
            Use binary search.  Don't treat it as a 2D matrix, just treat it as a sorted array
            m * n matrix convert to an array => matrix[x][y] => a[x * n + y]
            an array convert to m * n matrix => a[x] =>matrix[x / n][x % n];
            https://leetcode.com/discuss/15379/binary-search-on-an-ordered-matrix
            https://leetcode.com/discuss/10735/dont-treat-it-as-a-2d-matrix-just-treat-it-as-a-sorted-list
            */
            int m = matrix.length, n = matrix[0].length;
        int begin = 0, end = m * n - 1;
        
        while (begin <= end) {
            int mid = begin + (end - begin)/2 ;
            int mid_val = matrix[mid / n][mid % n];
            if (mid_val == target) {
                return true;
            } else if (mid_val < target) {
                //Should move a bit further, otherwise dead loop.
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return false;
    }
        
        
    // pass case 1 and 2, failed at case 3
    public static boolean searchMatrix_mine(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int rowUp = 0, rowDown = m-1, colLeft = 0, colRight = n-1;
        
        while(rowUp  <= rowDown ) {
            int mid = rowUp + (rowDown - rowUp)/2;
            int mid_val = matrix[rowUp][0] + (matrix[rowDown][n-1] - matrix[rowUp][0])/2;
            //System.out.printf("mid_val = %d ", mid_val);

            if (target == mid_val) {
                rowUp = mid;
                rowDown = mid;
                break;
            }
            else if (target > mid_val) {
                rowUp = mid + 1;
            } else {
                rowDown = mid -1;
            } 
           
        }
        
        while (colLeft <= colRight) {
            int mid = colLeft + (colRight - colLeft)/2;
            // System.out.printf("rowUp = %d, rowDown= %d \n", rowUp, rowDown);  
            // rowUp=1 , ArrayIndexOutOfBoundsException,  matrix[0][0] = -5 for case 3s
            //System.out.printf("colLeft = %d, colRight= %d\n", colLeft, colRight);
            int mid_val = matrix[rowUp][colLeft] + (matrix[rowUp][colRight] - matrix[rowUp][colLeft])/2;
            //System.out.printf("mid_val = %d\n", mid_val);
            if (target == mid_val ) return true;
            else if (target >  mid_val) {
                colLeft = mid + 1;
                System.out.printf("colLeft = %d, colRight= %d\n", colLeft, colRight);
            } else {
                colRight = mid ;
            }
            //System.out.printf("colLeft = %d, colRight= %d\n", colLeft, colRight);
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  //把这个数组当做一维数组处理，二分查找
  // [0, m*n - 1]
    if (matrix == '' || matrix == [])  return false;
    
    let m = matrix.length;
    let n = matrix[0].length;
    var start = 0;
    var end = m * n - 1;
    while (start <= end) {
        var mIdx = parseInt(start + (end - start) /2 );  // js 注意取整
        
        var median = matrix[parseInt(mIdx / n)][parseInt(mIdx % n)];
        if (median === target) return true;
        if (median < target) start = mIdx + 1;
        else end = mIdx - 1;
    }
    return false;
};