二维数组中的查找

剑指Offer - PHP /

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

分析

已知：行从左到右递增，列从上到下递增。
初始：数组初始查找位置位于左下角（即最后一行的第一个元素）
查找：如果 target（目标数）小于当前数组元素，说明要往上一行查找（因为右边是比它大的）；如果 target 大于当前数组元素，说明要往当前行的右边查找。

代码

    public function test()
    {
        $array  = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]];
        $target = 7;

        $arr_num     = count($array);     // 计算子数组个数
        $element_num = count($array[0]);  // 计算每个子数组的元素个数

        // 从数组的最后一个子数组的第一个元素开始
        $i = $arr_num - 1;
        $j = 0;
        while ($i >= 0 && $j < $element_num) {
            // 如果目标数等于当前数，返回 true
            if ($target == $array[$i][$j]) {
                return true;
            } elseif ($target < $array[$i][$j]) {
                // 如果目标数小于当前数，往上一行走
                $i--;
            } else {
                // 如果目标数大于当前数，往当前行的右边走
                $j++;
            }
        }
        // 没找到，返回 false
        return false;
    }