描述

寫出一個(gè)高效的算法來(lái)搜索 m × n矩陣中的值。
這個(gè)矩陣具有以下特性：
每行中的整數(shù)從左到右是排序的。
每行的第一個(gè)數(shù)大于上一行的最后一個(gè)整數(shù)。

樣例

考慮下列矩陣：

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

挑戰(zhàn)

O(log(n) + log(m)) 時(shí)間復(fù)雜度

思路

由于二維數(shù)組是按照嚴(yán)格的升序排列的，所以本題兩種解法：

代碼

1. 先對(duì)矩陣的行進(jìn)行模板二分法來(lái)求確定target處于哪一行，然后再對(duì)矩陣的列進(jìn)行二分法, 確定位置。

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix == null || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length;
        int column = matrix[0].length;

        int start = 0;
        int end = row - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] == target) {
                return true;
            }
            if (matrix[mid][0] < target) {
                start = mid;
            }
            if (matrix[mid][0] > target) {
                end = mid;
            }
        }
        if (matrix[end][0] <= target) {
            row = end;
        }
        else if (matrix[start][0] <= target) {
            row = start;
        }
        /* 此處應(yīng)注意,不能把else if 寫成if 因?yàn)槎鄠€(gè)if是連續(xù)執(zhí)行的，而數(shù)組中元素是升序排列的
         * matrix[end][0], >= matrix[start][0]的, 若不加else可能會(huì)出現(xiàn)row = end 卻被
         * row = start 覆蓋的情形
         */
        else {
            return false;
        }

        start = 0;
        end = column - 1;
        // start,end 前不能加int，因?yàn)榍懊嬉呀?jīng)定義過(guò)start和end了，
        // 變量可以重新賦值，但不能重新定義
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[row][mid] == target) {
                return true;
            }
            if (matrix[row][mid] < target) {
                start = mid;
            }
            if (matrix[row][mid] > target) {
                end = mid;
            }
        }
        
        if (matrix[row][end] == target) {
            return true;
        }
        if (matrix[row][start] == target) {
            return true;
        }
        return false;
    }
}

2. Binary Search Once

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
    
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
    
        int row = matrix.length;
        int column = matrix[0].length;
    
        int start = 0, end = row * column - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            // 關(guān)鍵代碼
            int number = matrix[mid / column][mid % column];
            if (number == target) {
                return true;
            } else if (number > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    
        return false;
    
    }
}