# Swift solution - Divide and Conquer, Binary Search

• ``````class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
if matrix.count < 1 {
return false
}

let m = matrix.count
let n = matrix[0].count

return helper(matrix, [0, 0], [m - 1, n - 1], target)
}

private func helper(_ matrix: [[Int]], _ upperLeft: [Int], _ lowerRight: [Int], _ target: Int) -> Bool {
if upperLeft[0] > lowerRight[0] || upperLeft[1] > lowerRight[1] || lowerRight[0] >= matrix.count || lowerRight[1] >= matrix[0].count {
return false
}
if lowerRight[0] - upperLeft[0] == 0 && lowerRight[1] - upperLeft[1] == 0 {
return matrix[upperLeft[0]][upperLeft[1]] == target
}

let rowMiddle = (upperLeft[0] + lowerRight[0]) >> 1
let colMiddle = (upperLeft[1] + lowerRight[1]) >> 1
let diff = matrix[rowMiddle][colMiddle] - target

if diff > 0 {
return helper(matrix, upperLeft, [rowMiddle, colMiddle], target) || helper(matrix, [upperLeft[0], colMiddle + 1], [rowMiddle, lowerRight[1]], target) || helper(matrix, [rowMiddle + 1, upperLeft[1]], [lowerRight[0], colMiddle], target)
} else if diff < 0 {
return helper(matrix, [upperLeft[0], colMiddle + 1], [rowMiddle, lowerRight[1]], target) || helper(matrix, [rowMiddle + 1, upperLeft[1]], [lowerRight[0], colMiddle], target) || helper(matrix, [rowMiddle + 1, colMiddle + 1], lowerRight, target)
}

return true
}

func searchMatrix_BinarySearch(_ matrix: [[Int]], _ target: Int) -> Bool {
if matrix.count < 1 || matrix[0].count < 1 {
return false
}

var col = matrix[0].count - 1
var row = 0

while col >= 0 && row <= matrix.count - 1 {
if target == matrix[row][col] {
return true
} else if target < matrix[row][col] {
col -= 1
} else {
row += 1
}
}

return false
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.