GoLang. True binary search. Two pointers
\n\n1.Diagonal binary search. Complexity O(ln(n) + ln(m))\n\n\nfunc searchMatrix(matrix [][]int, target int) bool {\n\n\tn, m := len(matrix), len(matrix[0])\n\n
\n\n**1.Diagonal binary search. Complexity O(ln(n) + ln(m))**\n\n```\nfunc searchMatrix(matrix [][]int, target int) bool {\n\n\tn, m := len(matrix), len(matrix[0])\n\n\tmin := func(i1 int, i2 int) int {\n\t\tif i1 < i2 {\n\t\t\treturn i1\n\t\t}\n\t\treturn i2\n\t}\n\t\n\tvar binarysearch func(x1 int, x2 int, y1 int, y2 int) bool\n\tbinarysearch = func(x1 int, x2 int, y1 int, y2 int) bool {\n\t\tif x1 > x2 || y1 > y2 {\n\t\t\treturn false\n\t\t}\t\n\t\tdelta := min(x2 - x1,  y2 - y1);\n\t\tlo1, lo2, hi1, hi2 := x1, y1, x1 + delta, y1 + delta\n\n\t\tfor lo1 <= hi1 && lo2 <= hi2 {\n\t\t\tm1 := lo1 + (hi1 - lo1) / 2\n\t\t\tm2 := lo2 + (hi2 - lo2) / 2\n\t\t\tv := matrix[m1][m2]\n\t\t\tif v == target {\n\t\t\t\treturn true\n\t\t\t} else if matrix[m1][m2] > target {\n\t\t\t\thi1 = m1 - 1\n\t\t\t\thi2 = m2 - 1\n\t\t\t} else {\n\t\t\t\tlo1 = m1 + 1\n\t\t\t\tlo2 = m2 + 1\n\t\t\t}\n\t\t}\n\t\treturn binarysearch(lo1, x2, y1, hi2) || binarysearch(x1, hi1, lo2, y2)\t\n\t}\n\n\treturn binarysearch(0, n-1, 0, m-1)\n}\n```\n\n**2. Two pointer approach. Complexity O(n + m)**\n```\nfunc searchMatrix(matrix [][]int, target int) bool {\n\n\tn, m := len(matrix), len(matrix[0])\n\ti, j := 0, m-1\n\t\n\tfor i < n && j >= 0 {\n\t\tv := matrix[i][j]\n\t\tif v == target {\n\t\t\treturn true\n\t\t} else if v > target {\n\t\t\tj -= 1\n\t\t} else { \n\t\t\ti += 1\n\t\t}\n\t\t\n\t}\n\treturn false\n}\n```
['Two Pointers', 'Binary Search', 'Go']