二维数组中的查找

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 782 | 阅读时长 ≈ 1 分钟

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


　　

解析：

把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案。

　　时间复杂度T=O(nlogn)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0; i<array.length; i++){ //一个for循环+二分查找
            int left = 0;
            int right = array[i].length-1;
            int mid;
            while(left<=right){
                mid = (left+right)/2;
                if(target<array[i][mid])
                    right = mid-1;
                else if(target>array[i][mid])
                    left = mid+1;
                else
                    return true;
            }
        }
        return false;
    }
}
---------------- The End ----------------
0%