4. 二維數組中的查找
題目鏈接
牛客網
題目描述
給定一個二維數組，其每一行從左到右遞增排序，從上到下也是遞增排序。給定一個數，判斷這個數是否在該二維數組中。
Consider the following matrix:
[[1, 4, 7, 11, 15],[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]
]Given target = 5, return true.
Given target = 20, return false.
解題思路
要求時間復雜度 O(M + N)，空間復雜度 O(1)。其中 M 為行數，N 為 列數。
該二維數組中的一個數，小于它的數一定在其左邊，大于它的數一定在其下邊。因此，從右上角開始查找，就可以根據 target 和當前元素的大小關系來快速地縮小查找區間，每次減少一行或者一列的元素。當前元素的查找區間為左下角的所有元素。
