二维数组中的查找

野性酷女 2022-06-07 01:59 210阅读 0赞

链接：[https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?orderByHotValue=1&questionTypes=000100&page=1&onlyReference=false][https_www.nowcoder.com_questionTerminal_abc3fe2ce8e146608e868a70efebf62e_orderByHotValue_1_questionTypes_000100_page_1_onlyReference_false]  
来源：牛客网

*  时间限制：1秒空间限制：32768K
 *  [算法知识视频讲解][Link 1]

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

分析：昨天刚好刷了leetcode上的[167. Two Sum II - Input array is sorted][]，数组有序，采用二分查找。这道题的二维数组也是有序的，所以很快就想到了采用二分查找算法。

基本思想是：行遍历二维数组，对每一行进行一次二分查找，直到找到目标值，直接返回true；否则返回false。使用flag作为标志位，初始值为false。外层循环进行行遍历，二位数组行数为array.length，因为二维数组每一行都是从左到右递增的，所以首先判断该行的最后一个数（该行的最大数）是否小于target（即array\[i\]\[array\[i\].length - 1\] < target），若小于target，则在该行一定找不到target值；否则的话就对该行进行二分查找，查找是否等于target，一旦找到就设置flag=true，并返回flag的值；否则继续判断下一行是否存在该整数，直至循环结束，返回flag的值（若循环结束都未找到，则flag一直为false）。

注意：开始查找前要判断二维数组是否为空。

java中判断数组为空，要检查三个部分:

一是数组首地址是否为空

二是是否为\{\}，也就是array.length==0的情况

三是\{ \{\}\}，这时array.length=1，但是array\[0\].length==0。满足任意一个条件就可以返回false了。

if(array==null||array.length==0||(array.length==1&&array\[0\].length==0)) return false;

判断二维数组是否为空参考：[http://www.cnblogs.com/daneres/p/6507535.html][http_www.cnblogs.com_daneres_p_6507535.html]

public class Solution {
        public boolean Find(int target, int [][] array) {
            if(array == null||array.length == 0||(array.length == 1 && array[0].length == 0))
                return false;
            int j = 0;
            boolean flag = false;
            for(int i = 0;i < array.length;){
                if(array[i][array[i].length - 1] < target){
                    i++;
                }
                else{
                    int bottom = 0;
                    int top = array[i].length - 1;
                    while(bottom <= top){
                        int mid = (bottom + top)/2;
                        if(array[i][mid] < target)
                            bottom = mid + 1;
                        else if(array[i][mid] > target)
                            top = mid - 1;
                        else
                            return true;
                    }
                    i++;
                }
            }
            return flag;
        }
    }

[https_www.nowcoder.com_questionTerminal_abc3fe2ce8e146608e868a70efebf62e_orderByHotValue_1_questionTypes_000100_page_1_onlyReference_false]: https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?orderByHotValue=1&questionTypes=000100&page=1&onlyReference=false
[Link 1]: http://write.blog.csdn.net/courses/semester/algorithm
[167. Two Sum II - Input array is sorted]: http://blog.csdn.net/wust_lh/article/details/78157481
[http_www.cnblogs.com_daneres_p_6507535.html]: http://www.cnblogs.com/daneres/p/6507535.html