vlambda博客
学习文章列表

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

下面的实例说明了二分查找的工作原理。我随便想一个1～100的数字，目标是你以最小的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。

假设你从你开始一次往上猜测，过程会是这样的。 

这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我的数字是99，你得猜99次才能猜到。

最佳的查找方式，从50开始。

小了，但排除了一半的数字！你知道1～50都小了。接下来，你猜75.

大了，，那余下的数字又排除了一半！使用二分法查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63(50-75中间的数字)。

这就是二分法查找。每次猜测排除的数字个数如下。不管我心里想的那个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！

假设你要在字典中查找一个单词，而该字典包含240000和单词，你认为每种查找最多需求多少步？

如果要查找的单词位于字典末尾，使用简单查找将需要240000步。使用二分查找时，每次排除一半单词，直到最后剩下一个单词。一般而言，对于包含n个元素的列表，用二分法查找最多需log_2(n)步，而简单查找最多需要n步。仅当列表有序的时候二分法才管用。

2 Python代码

假设找16，即程序中的N=16，运行结果

假设找N=10，运行

●

●

●

●

免责声明：部分资料来源于网络，转载的目的在于传递更多信息及分享，并不意味着赞同其观点或证实其真实性，也不构成其他建议。仅提供交流平台，不为其版权负责。如涉及侵权，请联系我们及时修改或删除。