package main

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	m, n := len(matrix), len(matrix[0])
	beg, end := 0, m*n-1
	for beg <= end {
		mid := (beg + end) / 2
		midVal := matrix[mid/n][mid%n]
		if target > midVal {
			beg = mid + 1
		} else if target < midVal {
			end = mid - 1
		} else {
			return true
		}
	}
	return false
}

/* func main() {
	m1 := [][]int{
		{1, 3, 6, 8},
		{9, 13, 53, 76},
		{99, 123, 243, 453},
		{654, 765, 876, 987},
	}
	fmt.Println(searchMatrix(m1, 987))
	fmt.Println(searchMatrix(m1, 97))
	fmt.Println(searchMatrix(m1, 1))
} */