题解 | #二维数组中的查找#

二维数组中的查找

http://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e

思路
遍历数组,区间分析,如果当前一维数组的左右值区间中可能包含target目标值,那么进行二分查找,如果不包含,那么continue。
其中需要注意,如果当前一维数组的最小数(第0个数)大于目标值target,那么直接宣布结束,返回false。

结果
耗时:143ms
占用内存:16900KB
代码

  public boolean Find(int target, int [][] array) {
        // 用于判断二维数组是否是空,[[]]即为空。
        if (array.length <= 0 || array[0].length <= 0)
            return false;
        for (int i = 0; i < array.length; i++) {
            // 如果当前数组的第一个数值小于目标值,那么将不会再有值与之匹配
            if (array[i][0] > target) return false;
            // 如果目标值在该数组的开始->结尾内,那么使用二分查找进行查找
            if (array[i][0] <= target && array[i][array[0].length - 1] >= target){
                // 二分查找
                int left = 0;
                int right = array[0].length - 1;
                int mid = left + ((right - left)>>1);
                while (left <= right){
                    if (array[i][mid] > target) right = mid - 1;
                    else if (array[i][mid] < target) left = mid + 1;
                    else {
                        System.out.println("位置:(" + (i+1) + "," + (mid+1) + ")");
                        return true;
                    }
                    mid = left + ((right - left)>>1);
                }
            }


        }
        return false;

    }
全部评论

相关推荐

fRank1e:吓得我不敢去外包了,但是目前也只有外包这一个实习,我还要继续去吗
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务