/** ✅
 * @Author: yirufeng
 * @Date: 2020/12/7 11:41 上午
 * @Desc:
 * 方法一：暴力
 * 方法二：从右上角或者左下角每次排除一行或者一列
 * 方法三：每一行二分搜索
 * 方法四：采用二分
		思路：获取当前搜索矩阵的中心点，然后排出左上角或者右下角的矩阵
	如下是方法四代码
 **/
func searchTarget(matrix [][]int, x1, y1, x2, y2, target int) bool {
	//递归可能越界
	if x1 > x2 || y1 > y2 {
		return false
	}

	//之前这个if语句块没有写会死循环，
	//注意点：避免x1，y1，x2，y2相等时调用searchTarget(matrix, x1, y1, xMid, yMid, target)死循环
	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)
}