在面试的过程中被问到的一个问题，如何从100万个邮箱地址（不重复）中获知某一指定邮箱是否存在于其中，如果存在，请给出其位置？

当时回答的不怎么好，面试过后又想了想这方面的问题，今天才回到家，趁热把题目和后来的思路记录下来。

从100万个不重复的邮箱地址中快速找到某个特定的邮箱地址，暂时考虑的方法有两种：

一、先排序，然后用二分搜索进行查找，该方法的时间复杂度在O(n·log₂n)这样的一个级别，主要时间花在了排序上面，常见的时间复杂度为O(n·log₂n)的排序算法（快速排序、归并排序、堆排序），排序之后的二分查找的时间复杂度在O(log₂n)，所以总的时间复杂度为O(n·log₂n)，这是比较容易想到的一种方法，但是效率不是最好的，所以会需要下面这种方法；

二、利用数组这样的一种键/值结构（也可以说和Python中的dict类型数据的键值对数据类型很像），只需要遍历一遍即可为所有的邮箱地址建立一个对应的位置信息，时间复杂度为O(n)，这样的话对于一个未排序的普通数据来说应该是最快的方法了，下面分别用awk、PHP、Python实现了对应的功能（因为这几种语言在建立动态数组/dict时不需要自己管理细节问题，但如果要用C语言实现的话除了需要动态申请内存之外，还有很多细节问题需要考虑，是比较麻烦的！）：

awk版本

数组下标从0开始：

awk 'BEGIN{i=0} {a[$1]=i++}; END{for (IP in a) print a[IP]"t", IP}' 404_ipList.txt

数组下标从1开始：

awk 'BEGIN{i=0} {a[$1]=++i}; END{for (IP in a) print a[IP]"t", IP}' 404_ipList.txt

测试效果如下：

# cat 404_ipList.txt
27.159.252.242
27.153.217.183
27.153.217.15

# awk 'BEGIN{i=0} {a[$1]=i++}; END{for (IP in a) print a[IP]"t", IP}' 404_ipList.txt
1 27.153.217.183
0 27.159.252.242
2 27.153.217.15

# awk 'BEGIN{i=0} {a[$1]=++i}; END{for (IP in a) print a[IP]"t", IP}' 404_ipList.txt
2 27.153.217.183
1 27.159.252.242
3 27.153.217.15

PHP版本

<?php
$all = file("email.txt");
$lines = array();
for($i=0; $i<count($all); $i++) {
    $all[$i] = trim($all[$i]);
    if($all[$i]) {
        $lines[$all[$i]] = $i; #思想：用Email地址来作为数组下标，行数为对应的数组元素的值
    }
}

// $temp = array_keys($lines);
// natsort($temp);	#自然排序
// print_r($temp);

Python版本

f = open('email.txt', 'r')
dic = {}
i = 1
while True:
	line = f.readline().strip()
	if len(line) != 0:
		dic[line] = i
		i + =1
f.close()

print(dic['[email protected]']) #打印出需要查找的Email地址的位置(从1开始计算)

先差不多就记录这么些吧，如果你有更好的方法或思路请不吝指教，谢谢。

PS：如果只是要达到这样的查找目的的话，在Linux下我一般用的是find、xargs、grep、parallel这几个命令的组合；在Windows下打开较大文件一般用的是EditPlus。

PS2：中午在看jobbole上的文章时，看到了“算法系列：计数排序”，我终于知道了原来这个算法有名字叫做：计数排序，但我这里说的和jobbole上的又稍有不同，思路是一样的，了解一下然后会用就行。