# Search a 2D Matrix ### Source - leetcode: [Search a 2D Matrix | LeetCode OJ](https://leetcode.com/problems/search-a-2d-matrix/) - lintcode: [(28) Search a 2D Matrix](http://www.lintcode.com/en/problem/search-a-2d-matrix/) ### Problem 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. #### Example Consider the following matrix: ~~~ [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] ~~~ Given `target = 3`, return `true`. #### Challenge O(log(n) + log(m)) time ### 題解 - 一次二分搜索 V.S. 兩次二分搜索 - **一次二分搜索** - 由于矩陣按升序排列，因此可將二維矩陣轉換為一維問題。對原始的二分搜索進行適當改變即可(求行和列)。時間復雜度為 O(log(mn))=O(log(m)+log(n))O(log(mn))=O(log(m)+log(n))O(log(mn))=O(log(m)+log(n)) - **兩次二分搜索** - 先按行再按列進行搜索，即兩次二分搜索。時間復雜度相同。 顯然我們應該選擇一次二分搜索，直接上 lower bound 二分模板。 ### Java ~~~ 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 || matrix[0] == null) { return false; } int ROW = matrix.length, COL = matrix[0].length; int lb = -1, ub = ROW * COL; while (lb + 1 < ub) { int mid = lb + (ub - lb) / 2; if (matrix[mid / COL][mid % COL] < target) { lb = mid; } else { if (matrix[mid / COL][mid % COL] == target) { return true; } ub = mid; } } return false; } } ~~~ ### 源碼分析 仍然可以使用經典的二分搜索模板(lower bound)，注意下標的賦值即可。 1. 首先對輸入做異常處理，不僅要考慮到matrix為null，還要考慮到matrix[0]的長度也為0。 1. 由于 lb 的變化處一定小于 target, 故在 else 中判斷。 ### 復雜度分析 二分搜索，O(logn)O(\log n)O(logn).