更新：此题解 markdown 源文件已放到 Github https://github.com/bytetopia/offer-coding-interviews-python (opens new window)，欢迎前去给个小星星鸭！

---

知识点：查找 复习：线性表顺序查找、二分查找

二维数组的查找

题目描述

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

分析

要充分利用题目中给定的有顺序这一条件，基本思路是从某个位置出发，利用数组大小的特点逐步缩减查找的空间。

每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，数组可能是这样的：

		1	2	8	9
		2	4	9	12
		4	7	10	13
		6	8	11	15

例如，从左下角出发，如果 current < target，而current已经是它所在列的最大，target不可能在current所在的列中了，指针可以向右移动一格，排除掉current所在的列；如果current<target，而current已经是它所在行的最小值了，target不可能在current所在的行中了，所以指针可以向上移动一格，排除掉current所在的行。

按照上述逻辑可以从左下角开始，按行或列逐渐缩减查找的空间。

从右上角开始同理。可以思考一下，如果从左上角或者右下角的话，就不能这样来判断了。

代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        # write code here
        if target is None or array is None:
            return False
        col = 0
        row = len(array)-1
        while row >= 0 and col < len(array[0]):
            if target == array[row][col]:
                return True
            elif target > array[row][col]:
                col += 1
            elif target < array[row][col]:
                row -= 1
        return False

回顾一下查找算法

平均查找长度ASL：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。 　　Ci：找到第i个数据元素时已经比较过的次数。

顺序查找

def Find(target, values):
    for i in range(0, len(values)):
        if values[i] == target:
            return True
    return False

ASL= 1/n * (1+2+3+…+n) = (n+1)/2 时间复杂度O(n)

二分查找

要求元素必须是有序的。 最坏的情况是查找到最后才找到，也就是经过了k次二分，n/(2^k)=1, n=2^k, k=log(n)，时间复杂度 O(log n)

通过循环实现：

def Binary(target, values):
    left = 0
    right = len(values) - 1
    while left <= right:
        mid = (left + right) // 2
        if values[mid] == target:
            return mid
        elif values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

通过递归实现：

def Binary_recursive(target, values, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if target == values[mid]:
        return mid
    elif target > values[mid]:
        return Binary_recursive(target, values, mid + 1, right)
    else:
        return Binary_recursive(target, values, left, mid - 1)

另外有一点是 在 mid = (left + right) // 2 这一句里面，如果是c语言可能会存在数值过大相加溢出的问题，可以用 mid = left + (right-left)//2 的写法