2020-11-15：手写代码：行有序、列也有序的二维数组中，找num，找到返回true，否则false？

福哥答案2020-11-15：

此题来源于leetcode240和剑指 Offer（第 2 版）面试题4。
1.线性查找。
从二维数组的坐下角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则上移。如果当前元素小于目标值，则右移。
2.线性查找+二分查找。
当前元素上移和右移，采用二分法。要用到如下两道题：
2.1.在一个有序数组中，找<=某个数最右侧的位置。
2.2.在一个有序数组中，找>=某个数最左侧的位置。

golang代码如下：

package main

import "fmt"

//https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
//https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
func main() {
    matrix := [][]int{
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30},
    }
    target := 15
    fmt.Println("线性查找：", findNumberIn2DArray1(matrix, target))
    fmt.Println("线性查找+二分查找：", findNumberIn2DArray2(matrix, target))
}

//线性查找
func findNumberIn2DArray1(matrix [][]int, target int) bool {
    N := len(matrix)
    if N == 0 {
        return false
    }
    M := len(matrix[0])
    n := N - 1
    m := 0
    for n >= 0 && m < M {
        if matrix[n][m] > target { //如果当前元素大于目标值，则上移
            //↑
            n--
        } else if matrix[n][m] < target { //如果当前元素小于目标值，则右移
            //→
            m++
        } else {
            return true
        }
    }
    return false
}

//线性查找+二分查找
func findNumberIn2DArray2(matrix [][]int, target int) bool {
    N := len(matrix)
    if N == 0 {
        return false
    }
    M := len(matrix[0])
    n := N - 1
    m := 0
    for n >= 0 && m < M {
        if matrix[n][m] > target { //在一个有序数组中，找<=某个数最右侧的位置
            //↑
            //n--
            UP := 0
            DOWN := n
            index := -1
            for UP <= DOWN {
                mid := UP + (DOWN-UP)>>1
                if matrix[mid][m] == target {
                    return true
                } else if matrix[mid][m] < target {
                    index = mid
                    UP = mid + 1
                } else {
                    DOWN = mid - 1
                }
            }
            if index == -1 {
                return false
            } else {
                n = index
            }

        } else if matrix[n][m] < target { //在一个有序数组中，找>=某个数最左侧的位置
            //→
            //m++
            LEFT := m
            RIGHT := M - 1
            index := -1
            for LEFT <= RIGHT {
                mid := LEFT + (RIGHT-LEFT)>>1
                if matrix[n][mid] == target {
                    return true
                } else if matrix[n][mid] > target {
                    index = mid
                    RIGHT = mid - 1
                } else {
                    LEFT = mid + 1
                }
            }
            if index == -1 {
                return false
            } else {
                m = index
            }
        } else {
            return true
        }
    }
    return false
}

执行结果如下：

image.png

有疑问加站长微信联系（非本文作者）