Golang solutions O(m+n) traversal and 2 dimensions binary search

• O(m+n) solution, the idea is well explained at here: https://discuss.leetcode.com/topic/20064/my-concise-o-m-n-java-solution. Honestly I could not come up with the solution until I read the thread.

``````func searchMatrix(matrix [][]int, target int) bool {
ylen := len(matrix)
if ylen == 0 {
return false
}
xlen := len(matrix[0])
if xlen == 0 {
return false
}

x, y := xlen-1, 0
current := matrix[y][x]

stop := false
for {
switch {
case current < target:
y++
stop = (y > ylen-1)
case current > target:
x--
stop = (x < 0)
default:
return true
}
if stop {
break
}
current = matrix[y][x]
}
return false

``````

2 dimensions binary search. We can drop 1/4 of the whole area each time, but a number of calls of recursive function increased by 3 times on every drop. I like this explanation: https://discuss.leetcode.com/topic/33240/java-an-easy-to-understand-divide-and-conquer-method

I think the complexity is `3^log4(mn)`? not so confident.

``````func searchMatrix(matrix [][]int, target int) bool {
ylen := len(matrix)
if ylen == 0 {
return false
}
xlen := len(matrix[0])

top, bottom, left, right := 0, ylen-1, 0, xlen-1
res := false
doSearch(&res, matrix, target, top, bottom, left, right)
return res
}

func doSearch(res *bool, matrix [][]int, target int, top, bottom, left, right int) {
if *res || bottom < top || right < left {
return
}
midy, midx := top+(bottom-top)/2, left+(right-left)/2
mid := matrix[midy][midx]
if mid == target {
*res = true
return
}

if mid < target {
doSearch(res, matrix, target, top, midy, midx+1, right)
doSearch(res, matrix, target, top+1, bottom, midx+1, right)
doSearch(res, matrix, target, top+1, bottom, left, midx)
return
}
doSearch(res, matrix, target, top, midy-1, left, midx-1)
doSearch(res, matrix, target, top, midy-1, midx, right)
doSearch(res, matrix, target, midy, bottom, left, midx-1)
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.