第11-12课查找问题¶

本节课，我们将专注在一个问题上：查找问题。什么是查找问题呢，本质上就是从一大堆杂乱或者不杂乱的东西中，找到我们想要的东西。抽象出来，从最基本的查找问题说起。

给定一个数组（数组内无重复数字），现在需要找到数n所在的位置，你会如何完成这个查找问题呢？

顺序查找（穷举法）¶

在我们前面学习的基础上，大家很快就能想到可以使用穷举法，使用循环一个个去尝试比较，这样最终就能找到数n的位置了。要注意的是，题目已经告诉我们数组中并无重复数字，所以找到后就可以直接中断。

很快我们可以写出代码：

def find(array, target):
    i = 0
    while __________:
        if ____________:
            print("{} is located at index {}".format(target, i))
            break
        i += 1

如果题目中的要求是重复数，那么你需要遍例所有可能。

符号表查找¶

在上面的问题中，还有没有什么方法能够更方便的找到我们的目标呢？我把题目稍做变化，改为：

给定一个数组array，数组中的数的范围是 0 到 10000，请写算法查找这个数组中是否含有目标数target。

解题思路

首先我们可以定义一个数组map，这个数组的长度是10001（为什么呢？因为数的范围是0-10000），并且默认为0。现在我们可以将在数组i位置处存储的数表示为i这个数在待查找数组array中出现的次数;
遍例数组，将每个数字出现的的次数统计到数组中。
查找数值时，直接取符号表中target位置的数。

def find(array, target):
    map = []
    i = 0
    while i <= 10000:
        map.append(0)
        i += 1

    i = 0
    while i < len(array):
        map[array[i]] += 1
        i += 1

    return map[target]

那如果需要找到目标数的坐标呢？

def find(array, target):
    map = []
    i = 0
    while i <= 10000:
        map.append([])
        i += 1

    i = 0
    while i < len(array):
        map[array[i]].append(i)
        i += 1

    return map[target]

思考题：¶

如果数的范围非常大，比如有\(0 - 2^{64} - 1\)那么大，那你就需要建立一个非常大的符号表，至少是需要\(2^{64}\)个整数的空间那么多，这是一个非常耗费内存的操作。你有什么办法能够改善这个问题吗？

在计算机中，我们一般使用字节(byte)做为存储容量的最小单位，1个字节占8个比特(bit)。容量之间的换算关系 - 1 KBytes = 1024 Bytes - 1 MBytes = 1024 KBytes - 1 GBytes = 1024 MBytes - 1 TBytes = 1024 GBytes - ...

在Python中，整数随着数大小的不同，占用内存是变化的。但是我们可以假设Python中1个整数占用4个字节（事实上现在的64位系统是8个字节），那你建立一个上面数范围的符号表需要多少内存呢，计算一下。

符号表的优缺点：¶

优点：建立完符号表后，每次查找的时候时间是固定的（只需要直接读表即可）；
缺点：占用额外内存。

二分查找¶

现在我们专注讨论一下有序数组的查找问题。如果现在有一个升序排列且没有重复数字的数组array，那么请编写函数find(array, target)，如果target存在于array中，请返回他的位置，否则请返回-1。

这个问题，其实我们可以用穷举法来解决，也可以用符号表的方法。但是注意到题目说了数组是有序的，那我们是不是可以稍加利用一下呢？

回想我们猜数字游戏，我们是不是也可以利用类似的方法去完成这个函数呢？

递推方法¶

def find(array, target):
    left = 0
    right = len(array) - 1

    while left <= right:
        mid = ________________
        if array[mid] < target:
            __________________
        elif array[mid] > target:
            __________________
        else:
            __________________

    return -1

递归方法¶

def find(array, left, right, target):
    if left > right:
        return -1

    mid = (left + right) // 2

    if array[mid] > target:
        return bind(array, left, mid - 1, target)
    elif array[mid] < target:
        return bind(array, mid + 1, right, target)

    else return mid

请你尝试计算一下，对于一个长序为N的数组来说，最坏情况下，需要查找多少次才能找到数字呢？

等比数列的求和公式

Matplotlib 初体验¶

简单的说，Matplotlib是一个用于绘图的Python库，他常常用于科学绘图，是学习数学和算法的好帮手。

安装¶

使用pip安装

pip install matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple

安装完成后我们可以先简单的绘制一条y=x的直线

import numpy as np
from matplotlib import pyplot as plt
x = np.arange(1, 11)
y = x
plt.plot(x, y)
plt.show()

同样，我们可以画一组折线图

import numpy as np
from matplotlib import pyplot as plt

x = [1, 3, 5, 8, 9]

plt.plot(x)
plt.show()

试试正弦图形

import numpy as np
from matplotlib import pyplot as plt

x = np.arange(0, 11, 0.1)
y = np.sin(x)

plt.plot(x, y)
plt.show()

大任务三、计算机猜数游戏：¶

请写一个猜数字游戏，与先前不同的是，这次是由你“生成”一个数字，而计算机来进行猜数字游戏；

你“生成”的数字的范围是 \(1 - 2^{32}-1\), 这个数字是4294967295；
当计算机猜出1个数时，请通过合适的输入方式告诉它是猜大了还是猜小了，还是计算机已经猜中了；
当一次猜数游戏结束时，你需要记录计算机猜数的次数；
让计算机玩20次猜数游戏，并记录计算机猜中所使用的次数；
请使用matplotlib画出计算机猜中次数的折线图；
请将计算机猜数的次数记录在下面的表格中。

No. 你生成的数字计算机猜测次数

1 123123123 10

2 12 20

3 13 14
撰写文档，将任务的思考过程和实现方法写出。最后要求附上计算机猜数程序、测试记录和图表。

No.	你生成的数字	计算机猜测次数
1	123123123	10
2	12	20
3	13	14

第11-12课 查找问题¶