剑指offer [01]二维数组的查找

C++

方法一：
每行查找，每一行从右向左查找。若array[i][j]大于target，则进入下一行。

    bool Find_1(int target, vector<vector<int> > array) 
    {
        if (array.empty()|| array[0].empty()) return false;
        int row = array.size();
        int col = array[0].size();
        if (target<array[0][0] || target>array[row - 1][col - 1]) return false;
        for (int i = 0; i < row; i++)
        {
            if (array[i].empty()) continue;
            else if (target >= array[i][0])
            {
                if (target <= array[i][array[i].size() - 1])
                {
                    for (int j = array[i].size() - 1; j >= 0; j--)
                    {
                        if (target == array[i][j])
                        {
                            cout << "行:"<< i <<"    "<< "列:" << j<<endl;
                            return true;
                        }
                        else if (target > array[i][j]) break;
                    }
                }
                else 
                {
                    continue;
                }
            }
            else return false;
        }
    }

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

bool Find_2(int target, vector<vector<int> > array)
{
    int row = array.size();
    for (int i = 0; i < row; i++)
    {
        int low = 0;
        int high = array[i].size() - 1;
        while (low <= high) 
        {
            int mid = (low + high) / 2;
            if (target > array[i][mid])
                low = mid + 1;
            else if (target < array[i][mid])
                high = mid - 1;
            else
            {
                cout << "行:" << i << "    " << "列:" << mid << endl;
                return true;
            }
        }
    }
    return false;
}

方法三：
利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素a[row][col]与target进行比较，当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,即col--；当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,即row++；

bool Find_3(int target, vector<vector<int> > array) 
{
    int row = 0;
    int col = array[0].size() - 1;
    while (row <= array.size() - 1 && col >= 0) 
    {
        if (target == array[row][col])
        {
            cout << "行:" << row << "    " << "列:" << col << endl;
            return true;
        }
        else if (target > array[row][col])
            row++;
        else
            col--;
   }
   return false;
}

python

方法一：
按行直接查找

class Solution:
    def Find(self, target, array):
        n = len(array)
        for i in range(n):
            if target in array[i]:
                return True
        return False

方法二：
（同C++方法三）

class Solution:
    def Find(self, target, array):
        # write code here
        rows = len(array) - 1
        cols= len(array[0]) - 1
        i = rows
        j = 0
        while j<=cols and i>=0:
            if target<array[i][j]:
                i -= 1
            elif target>array[i][j]:
                j += 1
            else:
                return True
        return False