剑指offer_01_二维数组中的查找

题目描述

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

解题思路

1 3 5 7
3 8 9 10
5 9 10 11
6 10 11 12
对于上面的一个矩阵，如果要查找一个数 k，如果当前(i, j)点的值为 v，当 k 大于 v，说明，k 的值在 v 的右边或者下边。如果小则在 v 的左边或者上边。查找可以从右上角的点开始查找，如果过k的值小，则移动到左边点，否则移动到下面的点（依次判断，直到找到或者越界）,当遇到k比v大时，不可能往右移动，因为右边没有数据了或者是刚才已经排除那个区域的值。

实现

public class Solution {
    public boolean Find(int [][] array,int target) {
        int rlen = array.length;
        if (rlen <= 0) {
            return false;
        }
        int clen = array[0].length;
        int rowIndex = 0;
        int colIndex = clen -1;
        while (rowIndex < rlen && colIndex >= 0){
            if (array[rowIndex][colIndex] == target) return true;
            else if (array[rowIndex][colIndex] > target){
                //去除该列，在该列的左边
                colIndex --;
            }else {
                //去除该行，在该行的下边
                rowIndex ++;
            }
        }
        return false;
    }
}