1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
func searchTarget(matrix [][]int, x1, y1, x2, y2, target int) bool { if x1 > x2 || y1 > y2 { return false }
if x1 == x2 && y1 == y2 { if matrix[x1][y1] == target { return true } return false }
xMid, yMid := x1+(x2-x1)>>1, y1+(y2-y1)>>1 if matrix[xMid][yMid] > target { return searchTarget(matrix, x1, y1, xMid, yMid, target) || searchTarget(matrix, x1, yMid+1, xMid-1, y2, target) || searchTarget(matrix, xMid+1, y1, x2, yMid-1, target) } else if matrix[xMid][yMid] < target { return searchTarget(matrix, x1, yMid+1, xMid, y2, target) || searchTarget(matrix, xMid+1, y1, x2, yMid, target) || searchTarget(matrix, xMid+1, yMid+1, x2, y2, target) } return true
}
func searchMatrix(matrix [][]int, target int) bool { if len(matrix) == 0 || len(matrix[0]) == 0 { return false } return searchTarget(matrix, 0, 0, len(matrix)-1, len(matrix[0])-1, target) }
|