剑指offer解题系列01

第一题

题目描述

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

题目来源于此。

分析

对于上面一个二维数组来说，左上角最小，右下角最大，可以使用变形的二分法沿着对角线来查找。

分析草稿

假设一个函数，对比左上角及右下角和目标的大小，若大于右下角或小于左上角，则不在该集合之内。

伪代码

class Solution:
    NOT_EXSIT = -2
    EXSIT = 2

    def cmp(self, target, array, startRow=-1, startCol=-1 row=-1, col=-1):
        if row == -1 or col == -1:
            col = len[array]
            row = len[array[0]]
        if startRow == -1 or startCol == -1:
            startRow = 0
            startCol = 0

        if (array[col - 1][row - 1] < target) or (array[col - 1][row - 1] > target):
            return NOT_EXSIT
        elif startRow == row and startCol == col:
            # 说明只能存在于本行本列之中了，搜索本行本列，得出最后答案
            # 对于array[col][row]这两个一维数组再次进行二分法
        else:
            # 表示存在于该范围内，准备下一轮轮询
            nextStartRow = (row - startRow) / 2
            nextStartCol = (col - startCol) / 2
            return self.cmp(target, array, nextStartRow, nextStartEnd)

解法

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here