剑指offer 第二章，面试题3：

一、题目：

二、题目考的是什么

2.1、此题考查对数组的查找。

2.2、数组特性：

数组中的内存是连续的，可以根据下标在O(1)时间读/写任何元素，因此它的时间效率很高。

三、解题思路

3.1，思路1

首先肯定是不能，一个一个，从第一行，从左到右索引的。时间复杂度太高。

我们解决一个复杂的问题时，一个很有效的办法就是从一个具体的问题入手，通过分析简单具体的例子，找寻普遍的规律。因此，对于这个问题，我们也从一个具体的例子入手。一步步分析查找的过程。

比如对于上面的问题，假设我们想要查找数字7。

根据数组的性质，初步想法是，从左上角开始，选择第一行的第一个数，如果比7小，那就向右查找，如果比7大，则向右向下都找不到7，搜索结束。但是，这个方法，跟一个一个从第一行从左向右查找没有区别。

3.2，思路2

试试随机选取一个数，根据与7比较大小，然后根据性质来进行下一步搜索。此时会有三种情况，都要考虑进去：

正好等于7，返回True
小于7，那么可以判断，7可能存在于该数的右边，以及该数的下边。下一步，应该在列数（或者行数）大于当前数的情况下进行判断查找。若是同样随机查找，那么，十分麻烦，甚至没有头绪。
大于7，同上小于7的分析。
因此，这个思路，并不合适，十分麻烦。

3.3，思路3

按照第一种思路的启发，若是该行的第一个数字比7大，那么说明此行的数都比7大，当然此行是找不到数字7的。
于是，启发我们，可以从左下角开始查找，同样有三种情况：

正好等于7，返回True
左下角的数比7大，说明此行都比7大，则舍弃在此行进行查找
比7小，那就说明此列的数，都比7小，就舍弃在此列进行查找
按照上述三个步骤不断循环，二维数组会越来越小，直到找到数字7。

同样的，按照从右上角开始查找数字7，不断减小查找范围，也是可以的。

测试：

功能测试：基础功能测试，输入其中有的数，其中没有的数，走一遍，看看每一步有没有逻辑错误。
边界测试：这里暂时用不到
特殊输入测试：输入为None，空列表[ ]也为None。

3.4，写代码

解法1：用递归写出代码。


    def searchMatrix( matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        #边界测试，如果输入只是一个空列表[]
        if  not matrix:
            return False
        
        #假设数组中没有此数，最终matrix会是这样的[[]]，此时是一个列表里面包含一个空列表，
        #注意此时matrix并不是空，因为matrix[0] = []，是有东西的
        if  not matrix[0]:
            return False
        
        #获取数组的行
        row_num = len(matrix)
        
        #选取左下角数字进行比较，判断，并执行下一步
        predict = matrix[row_num-1][0]
        if predict == target:
            return True
        elif predict > target:
            #删除掉该行，并且递归return searchMatxix（...）
            del matrix[row_num-1]
            return searchMatrix(matrix,target)
        else:
            #删除掉第0列所有元素
            for item in matrix:
                del item[0]
            return searchMatrix(matrix,target)

上面利用递归，并且是每次删掉matrix中的一些元素，直到最后找到或者matrix为空列表[]。

################################################################

还有另一种方式：
数组中索引，是 O(1)时间复杂度，所以即使不删掉行列，也是可以一步索引到元素的，因此可以只用索引的方法。

用循环
不删除matrix中的数，只是改变对行，或者列的索引。
这样就不会因为删除列元素而头疼了。

解法2：用循环来做

功能代码：
一开始，获取行数，列数。并从行列数开始索引。
选取左下角，仍然是有三种情况：

若是相等，则返回True
大于7，则行索引减1，索引到上一行
小于7，则列索引减1，索引到右侧一列
若是循环完毕也不存在，则返回False

为了不那么麻烦，需要用3个return，可以在循环外设置一个变量bool_found并初始化为False。若是在循环中找到target，则把变量赋值为True，并且break，否则就循环到底，并且不改变bool_found的值。

边界代码：用不到

特殊输入代码：，若是输入为一个空列表[ ]，或者是一个[ [] ]，要直接返回False。

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        #特殊输入测试
        if not matrix:
            return False
        
        bool_found = False
        row_num = len(matrix)
        line_num = len(matrix[0])
        
        r_cirle = row_num
        l_cirle = 0
        
        #当矩阵不为空，且不为[ [] ]形式时，也就是mat[0]不为空时，可以继续循环
        #写完之后，考虑一下，target在mat里，target不在mat的情况，确认没有问题了再提交代码
        while  r_cirle >= 0 and l_cirle <= line_num-1:
            #索引不能出错，要减一
            predict = matrix[r_cirle-1][l_cirle]
            if predict == target:
                bool_found = True
                break
            elif predict > target:
                r_cirle -= 1
            else:
                l_cirle += 1
        
        return bool_found
    #写完以后，测试一下True跟False的情况，看看是不是满足功能

数组----二维数组中数的查找2