题目描述
给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？
解答思路
方法一：分治法
依然可以用分治法解决，方法与前面类似，就不再次赘述了。
方法二：位图法
由于 unsigned int 数字的范围是 [0, 1 << 32)，我们用 1<<32=4,294,967,296 个 bit 来表示每个数字。初始位均为 0，那么总共需要内存：4,294,967,296b≈512M。
我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。
方法总结
判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。
