【題目描述】
Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.
This matrix has the following properties:Integers in each row are sorted from left to right.Integers in each column are sorted from up to bottom.No duplicate integers in each row or column.
寫出一個高效的算法來搜索m×n矩陣中的值，返回這個值出現(xiàn)的次數(shù)。
這個矩陣具有以下特性：每行中的整數(shù)從左到右是排序的。每一列的整數(shù)從上到下是排序的。在每一行或每一列中沒有重復(fù)的整數(shù)。
【題目鏈接】
http://www.lintcode.com/en/problem/search-a-2d-matrix-ii/
【題目解析】
O(m + n)解法：
從矩陣的右上角(屏幕坐標(biāo)系）開始，執(zhí)行兩重循環(huán)
外循環(huán)遞增枚舉每行，內(nèi)循環(huán)遞減枚舉列
O(n ^ 1.58)解法：
分治法，以矩形中點(diǎn)為基準(zhǔn)，將矩陣拆分成左上，左下，右上，右下四個區(qū)域
若中點(diǎn)值 < 目標(biāo)值，則舍棄左上區(qū)域，從其余三個區(qū)域再行查找
若中點(diǎn)值 > 目標(biāo)值，則舍棄右下區(qū)域，從其余三個區(qū)域再行查找
時間復(fù)雜度遞推式：T(n) = 3T(n/2) + c
【參考答案】
