题目
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
写一个搜索M 乘N矩阵的高效率方法，矩阵有以下特性：
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
For example,
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]
]
思想
因为矩阵在行与列是有序的，根据它的特性，左上角的数值A和右下角的数值B决定了矩阵的上界和下界。如果target不在区间[A, B]之中，说明肯定不存在这个矩阵里面。
-
把矩阵每次都分成4份，然后用小矩阵的上下界来判断target是否有可能在里面。如果有可能在的话，则继续分成4份，递归查找。如果没有可能的话，就停止，不需要再找了。
区间上下界 递归结束条件：最终只有一行或者一列的时候，是不可能再分了，这个时候就需要一个个比较判断target是否存在了。
实现
假设一开始数组的坐标为(SR, SC) ，而数组行数为RL，列数为CL， 则坐标如下图所示：
拆分视图
判断target是否有可能在某个区间内
我们只需要让target与(SR, SC) 和 (SR + RL - 1, CR + CL - 1)的元素值进行比较，就可以判断target是否有可能在该方格中。
/// 判断target是否在该区间中
///
/// - Parameters:
/// - matrix: 二维数组
/// - target: target
/// - rowStartIndex: 起始行下标
/// - columnStartIndx: 起始列下标
/// - row: 区间行数
/// - column: 区间列数
/// - Returns: 是否可能存在该区间中
func isTargetInRange(_ matrix:[[Int]], _ target: Int, rowStartIndex: Int, columnStartIndx: Int, row: Int, column: Int) -> Bool {
if target < matrix[rowStartIndex][columnStartIndx] || target > matrix[rowStartIndex + row - 1][columnStartIndx + column - 1] {
return false
}
return true
}
拆分区间
将一个大的区间拆分成4份小区间，也就是取行数、列数的一半，然后下标则如下图所示：
拆分下标
直接搜索
当区间的行数或者列数变成1的时候，已经不能再进行拆分了，这时候就可以直接遍历搜索了。如果已经找到了target则直接返回，而无需在别的区间寻找，方法的isFound变量就是这个作用。
最后搜索的方法如下：
/// 是否在该区间找到target
///
/// - Parameters:
/// - matrix: 二维数组
/// - target: target
/// - rowStartIndex: 起始行下标
/// - columnStartIndx: 起始列下标
/// - row: 区间行数
/// - column: 区间列数
/// - Returns: 是否在该区间找到target
func searchTarget(_ matrix:[[Int]], _ target: Int, rowStartIndex: Int, columnStartIndx: Int, row: Int, column: Int) -> Bool {
let isIn = isTargetInRange(matrix, target, rowStartIndex: rowStartIndex, columnStartIndx: columnStartIndx, row: row, column: column)
if !isIn {
return false
}
if row == 1 {
// 一横的情况
for item in matrix[rowStartIndex] {
if item == target {
return true
}
}
return false
}
else if column == 1 {
// 一竖的情况
for index in 0..<row {
if target == matrix[rowStartIndex + index][columnStartIndx] {
return true
}
}
return false
}
// 这里需要继续递归
let newRow = row / 2
let newColumn = column / 2
// 总共4个递归
// 是否已经找到的标志，如果找到了，就不需要再去别的区间找了。
var isFound = false
// 左上方
isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex, columnStartIndx: columnStartIndx, row: newRow, column: newColumn)
if isFound {
return isFound
}
isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex + newRow, columnStartIndx: columnStartIndx, row: row - newRow, column: newColumn)
if isFound {
return isFound
}
// 右上方
isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex, columnStartIndx: columnStartIndx + newColumn, row: newRow, column: column - newColumn)
if isFound {
return isFound
}
// 右下方
isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex + newRow, columnStartIndx: columnStartIndx + newColumn, row: row - newRow, column: column - newColumn)
return isFound
}
