Search a target value on a n*m matrix in Go (GoLang) with three different approaches.

search-matrix.go

package matrix

// BinarySearch searches `target` in `matrix`
// with the "binary search" algorithm.
// It returns its position if found or `-1, -1` if not found.
func BinarySearch(matrix [][]int, target int) (int, int) {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return -1, -1
    }

    for idx, row := range matrix {
        if size := len(row)-1; target <= row[size] {
            for left, right := 0, size; left <= right; {
                pos := left + (right-left)/2
                if row[pos] == target {
                    return idx, pos
                } else if row[pos] < target {
                    left = pos + 1
                } else /* if row[pos] > target */ {
                    right = pos - 1
                }
            }
        }
    }

    return -1, -1
}

// BinarySearch2 searches `target` in `matrix`
// with the "binary search" algorithm with a second approach.
// - Convert an n * m matrix to a slice (array): `matrix[x][y]` => `slice[x * m + y]`
// - Convert a slice (array) to an n * m matrix: `slice[x]` => `matrix[x / m][x % m]`
// It returns its position if found or `-1, -1` if not found.
func BinarySearch2(matrix [][]int, target int) (int, int) {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return -1, -1
    }

    var rows, cols int = len(matrix), len(matrix[0])
    var row, col int = 0, cols-1
    
    for row < rows && col >= 0 {
        var curr int = matrix[row][col]
        if curr == target {
            return col, row
        } else if curr < target {
            row++
        } else /* if curr > target */ {
            col--
        }
    }
    
    return -1, -1
}

// Search searches `target` in `matrix`
// without the "binary search" algorithm.
// For learning purposes only.
// It returns its position if found or `-1, -1` if not found.
func Search(matrix [][]int, target int) (int, int) {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return -1, -1
    }

    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1
    for left != right {
        if pos := (left+right-1)/2; matrix[pos/n][pos%n] < target {
            left = pos + 1
        } else {
            right = pos
        }
    }
    
    var x, y int = right/n, right%n 
    if matrix[x][y] != target {
        return -1, -1
    }
   
    return x, y
}