240. 搜索二维矩阵 II

240. 搜索二维矩阵 II

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        for (int i = 0; i < matrix.length; i++)
            for (int j = 0; j < matrix[0].length; j++)
                if (matrix[i][j] == target)
                    return true;
        return false;
    }
}

二分查找

func searchMatrix(matrix [][]int, target int) bool {
    for i := 0; i < len(matrix); i++ {
        if binarySearch(matrix[i], target) {
            return true
        } 
    }    
    return false
}
func binarySearch(nums []int, target int) bool {
    left, right := 0, len(nums) - 1
    for left <= right {
        mid := (left + right) / 2
        if (nums[mid] == target) {
            return true
        } else if (nums[mid] > target) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return false
}

题解: Z字形搜索

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    x, y := 0, n - 1
    for x < m && y >= 0 {
        if matrix[x][y] == target {
            return true
        } 

        if matrix[x][y] < target {
            x++
        } else {
            y--
        }
    }

    return false
}