【剑指Offer】二维数组中的查找（C/C++描述）

题目描述

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

• 思路一

1. 让target与数组最右上角（左下角类似）比较，若相等则返回true
2. 若target > nums[top][right]，则说明应该在该行下方找，故top++
3. 若target < nums[top][right]，则说明应该在该行左方找，故right--

• 思路二

1. 对每一行进行二分查找，找到则返回，找不到，找下一行，直到行结束

C语言描述

bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) 
{
    if(matrix == NULL || matrixColSize == NULL || matrixRowSize == 0)
    	return false;
    int right = matrixColSize-1, top = 0;
    while(top < matrixRowSize && right >= 0)
    {
    	if(matrix[top][right] == target)
    		return true;
    	else if(matrix[top][right] < target)
    	{
    		top++;
    	}
    	else if(matrix[top][right] > target)
    	{
    		right--;
    	}
    }
    return false;
}

C++描述 

class Solution 
{
public:
    bool Find(int target, vector<vector<int> > array) 
    {
        if( array.size()==0 )
            return false;
        if( array[0].size()==0)
            return false;
        int right = array[0].size()-1, top = 0;
        while(top < array.size() && right >= 0)
        {
            if(array[top][right] == target)
                return true;
            else if(array[top][right] < target)
            {
                top++;
            }
            else if(array[top][right] > target)
            {
                right--;
            }
        }
        return false;
    }
};