題目鏈接：https://leetcode-cn.com/problems/search-a-2d-matrix/submissions/

題解匯總：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

---

題目描述

編寫一個高效的算法來判斷 m x n 矩陣中，是否存在一個目標值。該矩陣具有如下特性：

每行中的整數從左到右按升序排列。
每行的第一個整數大于前一行的最后一個整數。

示例 1：
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true

示例 2：
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false

---

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky -------Knuth翻譯：盡管二分查找的基本理念十分簡單明了，但是它的細節queue令人抓狂 ----唐納德·克努特(KMP發明者)

發現了一個寶藏up，他的二分查找模板考慮到了二分查找幾乎所有的細節，包括死循環、越界等等，視頻地址：https://www.bilibili.com/video/BV1d54y1q7k7?from=search&seid=17631535455427077045&spm_id_from=333.337.0.0

class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty()) return false;int row = matrix.size(), col = matrix[0].size();int len = row * col;int l = -1, r = len, m;while(l + 1 != r) {m = (l + ((r - l)>>1));if (matrix[m/col][m%col] <= target) l = m; // 這里m-1一定注意考慮m是否可能為-1else r = m;}if (l == -1) return false; // 特殊情況if (matrix[l/col][l%col] == target) return true;else return false;} };

---

??????——這就是我喜歡算法的原因。在我眼里，算法從來不是枯燥的邏輯堆砌，而是神一樣的邏輯創造。盡管這個世界很復雜，但竟也如此的簡潔，優雅。

總結

以上是生活随笔為你收集整理的【二分法万能模板】Leecode 74. 搜索二维矩阵——Leecode日常刷题系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。