leetcode-go/leetcode/medium/240.search-a-2d-matrix-ii.go

func searchMatrix(matrix [][]int, target int) bool {
	yEnd := len(matrix)
	if yEnd == 0 {
		return false
	}
	xEnd := len(matrix[0])
	return searchPartOf(matrix, 0, xEnd, 0, yEnd, target)
}

func searchPartOf(matrix [][]int, xBeg, xEnd, yBeg, yEnd, target int) bool {
	m, n := yEnd-yBeg, xEnd-xBeg
	if m == 0 || n == 0 {
		return false
	}
	if m == 1 { // If m is 1 or n is 1, fall back to binary search.
		beg, end := xBeg, xEnd
		for beg < end {
			mid := beg + (end-beg)/2
			if matrix[yBeg][mid] < target {
				beg = mid + 1
			} else if target < matrix[yBeg][mid] {
				end = mid
			} else {
				return true
			}
		}
		return false
	} else if n == 1 {
		beg, end := yBeg, yEnd
		for beg < end {
			mid := beg + (end-beg)/2
			if matrix[mid][xBeg] < target {
				beg = mid + 1
			} else if target < matrix[mid][xBeg] {
				end = mid
			} else {
				return true
			}
		}
		return false
	}
	if target < matrix[yBeg][xBeg] || matrix[yEnd-1][xEnd-1] < target {
		return false
	}
	xMid, yMid := xBeg+(xEnd-xBeg)/2, yBeg+(yEnd-yBeg)/2
	return searchPartOf(matrix, xBeg, xMid, yBeg, yMid, target) || // Split the whole matrix into 4 parts.
		searchPartOf(matrix, xMid, xEnd, yBeg, yMid, target) ||
		searchPartOf(matrix, xBeg, xMid, yMid, yEnd, target) ||
		searchPartOf(matrix, xMid, xEnd, yMid, yEnd, target)
}