劍指offer：二維數組中的查找

目錄

• 題目
• 解題思路
• 具體代碼

題目

題目鏈接
劍指offer：二維數組中的查找
題目描述
在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

解題思路

這題解題的關鍵在于數據是有序的，很自然的便想到使用二分法；在提交后在評論區發現了更優的解法（除了數據有序外，利用了數據按矩陣形式排列這一特點），會在下列代碼中給出。
在使用二分法時，值得注意的是，不能將二維數組中所有元素看作單調遞增排列的一維數組，從而對所有元素整體進行二分。題目僅說明數據在矩陣的每行每列各自具單調遞增的性質；而行（或列）之間并沒有確定的大小關系。例如，第一行可能是[4, 5, 6], 而第二行為[1, 2, 3]，第二行元素可能小于第一行元素。

具體代碼

1. 二分法
因為只能逐行進行二分，故算法時間復雜度為O(nlogm)，n為矩陣行數，m為列數。
計算二分的中值mid時，推薦使用mid = (right - left) / 2 + left而不是mid = (left + right) / 2 ，這樣能夠避免加法溢出

class Solution {
public:bool Find(int target, vector<vector<int> > array) {// 求出矩陣行數row和列數colint row = array.size();int col = array[0].size();int left;int right;int mid;// 對數組逐行進行二分查找for (int i = 0; i < row; i++) {left = 0;right = col - 1;while (right >= left) {mid = (right - left) / 2 + left; // 防止left+right導致加法溢出if (array[i][mid] < target) {left = mid + 1;} else if (array[i][mid] > target) {right = mid - 1;} else {return true;}}}return false;}
};

2. 利用元素特殊的排列
利用元素排列的性質，對于左下角的元素來說，其同列上方的元素一定是小于它，其同行右方的元素一定是大于它；能夠在推導的過程中跳過更多的錯誤元素。易知，算法時間復雜度為O(n+m)

class Solution {
public:bool Find(int target, vector<vector<int> > array) {// 求出矩陣行數row和列數colint row = array.size();int col = array[0].size();// 初始從矩陣左下方開始查找for (int i = row - 1, j = 0; i >= 0 && j < col; ) {// 分三種情況// 1. 當前位置元素大于目標位置元素，位置上移一行(i--)// 2. 當前位置元素小于目標位置元素，位置右移一列(j++)// 3. 當前位置元素等于目標位置元素，已找到，返回trueif (target < array[i][j]) {i--;} else if (target > array[i][j]) {j++;} else {return true;}}return false;}
};