Golang, binary search solution, very very easy to understand.


  • 0
    func searchMatrix(matrix [][]int, target int) bool {
        // binary search to find row
        sr := 0
        er := len(matrix)-1
        
        left_bound := 0
    
        for sr <= er {
            mid := (sr + er) / 2
            v := matrix[mid][0]
            if target == v {
                return true
            } else if target < v {
                er = mid - 1
            } else {
                // target > v
                left_bound = mid
                sr = mid + 1
            }
        }
    
        sc := 0
        ec := len(matrix[left_bound]) - 1
        
        for sc <= ec {
            mid := (sc + ec) / 2
            v := matrix[left_bound][mid]
            if target == v {
                return true
            } else if target < v {
                ec = mid - 1
            } else {
                sc = mid + 1
            }
        }
        
        return false
    }
    

  • 0
    R

    Simpler and more compact binary search solution:

    func searchMatrix(matrix [][]int, target int) bool {
            if matrix == nil || len(matrix) < 1 || len(matrix[0]) < 1 { return false }
            row_num := len(matrix)
            col_num := len(matrix[0])
            
            begin, end := 0, row_num * col_num - 1
            
            for begin <= end {
                mid := (begin + (end - begin) / 2)
                mid_value := matrix[(mid/col_num)][mid%col_num]
                
                if mid_value == target { 
                    return true
                } else if mid_value < target {
                    begin = mid + 1
                } else {
                    end = mid - 1
                }
            }
            return false
    }
    

Log in to reply
 

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