package main

import "fmt"

func main() {
	var matrix = [][]int{
		{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},
	}

	// var matrix = [][]int {{-1, 3}}
	var find = searchMatrix(matrix, 20)
	fmt.Println(find)
}

func searchMatrix(matrix [][]int, target int) bool {
	var m = len(matrix)
	var n = len(matrix[0])

	var i, j int = m - 1, 0
	var min int = matrix[0][0]
	if min > target {
		return false
	} else if min == target {
		return true
	}

	var find bool = false
	for i >= 0 && j <= n-1 {
		if target < matrix[i][j] {
			i--
		} else if target > matrix[i][j] {
			j++
		} else {
			find = true
			break
		}
	}
	return find
}