[Python3算法(2)] 比较简单查找与二分查找[TZZ]

1、启动PyCharm软件，新建一个名为“AlgorithmDemo2”的“Pure Python项目”，然后向新创建的项目中添加一个名为“main”的Python文件；

2、在“main.py”文件中，分别定义10个元素、100个元素和10000个元素的列表。然后，为这3个列表填充自然数；

3、继续在“main.py”文件中定义一个linear_search的查找函数。在该函数中，总是从输入列表的第1个元素开始，依次遍历列表中的所有元素，直到找到目标元素为止。另外，该函数中额外增加了一个count变量，用于记录查找的总次数；

4、继续向“main.py”文件中添加测试linear_search函数的代码，然后调试运行程序。在测试代码中，采用了一个列表和一个字典将最初定义的3个测试列表关联起来。然后通过循环执行所有列表最坏情况下的查找任务；

5、当程序启动之后，在弹出的Console窗口中，可以见到每个列表的测试输出信息。随着列表长度的增加，最坏情况下，简单查找次数也会线性增加；

6、关闭Console窗口返回到“main.py”文件中，继续定义一个二分查找函数“binary_search”。该函数中也同时返回了查找的进行次数；

7、继续向“main.py”文件中添加“使用binary_search函数查找3个列表中最大元素”的测试代码。然后调试运行程序。在弹出的Console窗口中，可以见到二分查找算法在同样情况下，比简单查找使用查找次数要少得多。尤其是在搜索列表急剧增大时，差别更明显；

8、通常采用大O表示法来衡量算法的快慢，其表示形式为“O(x)”。此表示法表示的仅仅是算法在处理n个数据时，最坏情况下的操作数（执行某些操作的总次数，比如查找次数）（大O时间的单位可以理解为“次数”，并非传统的“秒”之类的时间单位）。另外，在实际情况下，该表示法对应的也只是一个近似值。如果需要估算代码的执行总时间，需要根据指令执行时长和单次操作的代码条数进行估算；

9、对于简单查找而言，其大O时间为“O(n)”。而对于二分查找而言，其大O时间则为“O(logn)”（这里的logn是以2为底的对数）。显然，二分查找的速度比简单查找要快得多。两种算法的比较就介绍到这里了，Enjoy！