成都网站线上公司,网页三剑客是哪三个软件,铭万做的网站怎么样,汕头房地产网二分查找
假设你需要在电话簿中找到一个以字母 “K” 开头的名字#xff08;虽然现在谁还在用电话簿呢#xff01;#xff09;。你可以从头开始翻页#xff0c;直到进入以 “K” 打头的部分。然而#xff0c;更明智的方法是从中间开始#xff0c;因为你知道以 “K” 打头…二分查找
假设你需要在电话簿中找到一个以字母 “K” 开头的名字虽然现在谁还在用电话簿呢。你可以从头开始翻页直到进入以 “K” 打头的部分。然而更明智的方法是从中间开始因为你知道以 “K” 打头的名字很可能在电话簿的中间部分。
类似地当你要在字典中查找一个以字母 “O” 开头的单词时你也会从中间附近开始搜索。
再举一个例子当你登录 Facebook 时系统需要核实你是否有该网站的账户。它必须在数据库中查找你的用户名。如果你的用户名是 “karlmageddon”Facebook 可以从以字母 “A” 开头的部分开始查找。然而更聪明的做法是从中间开始查找。
这些场景都涉及到查找问题而在所有这些情况下都可以使用同一种算法来解决那就是二分查找。
二分查找是一种算法它的输入是一个有序元素列表必须有序的原因稍后解释。如果要查找的元素包含在列表中二分查找会返回其位置否则返回 -1。
下面的示例演示了二分查找的工作原理。我们随意选择一个在 1 到 100 之间的数字。 你的目标是以最少的猜测次数猜到这个数字。每次猜测后我会告诉你是小了、大了还是猜对了。如果你从 1 开始顺序猜测过程可能是这样的
猜测 1 - 小了猜测 2 - 小了猜测 3 - 小了…
这种方法被称为简单查找更确切地说是傻找。每次猜测只能排除一个数字。如果数字是 99你最多需要猜测 99 次才能猜对。
更聪明的查找方法
下面是一种更聪明的猜测方法从 50 开始。
猜测 50 - 小了但排除了一半的数字现在你知道 1 到 50 都是小了。接下来你猜 75。猜测 75 - 大了又排除了一半的数字使用二分查找你猜测的是中间的数字从而每次都可以排除一半的数字。然后你猜测 6350 和 75 之间的数字。
这就是二分查找你刚刚学会了一种全新的算法每次猜测都会排除一半的数字如下图所示 不论我心里想的是哪个数字你最多需要 7 次猜测就能找到因为每次猜测都会排除很多数字。对比一下
简单查找100 步二分查找7 步
也许在使用者的角度看这 97 步的差距似乎微不足道。然而随着元素数量的增加二分查找的优势会越来越明显。
现在让我们考虑一个问题如果你要在包含 240,000 个单词的字典中查找一个单词最多需要多少步假设要查找的单词位于字典的末尾使用简单查找将需要 240,000 步。而如果使用二分查找每次都会排除一半的单词直到最后只剩下一个单词。
在进行二分查找时每次排除的单词数量是通过将搜索范围减半来计算的。因为字典中有 240,000 个单词每次排除一半我们可以计算出每次排除的单词数量如下
初始范围240,000 个单词第 1 次排除120,000 个单词第 2 次排除60,000 个单词…后续步骤省略
因此使用二分查找最多需要 18 次排除就能找到一个特定单词即使在包含 240,000 个单词的字典中。这是因为每一次排除一半的单词使得搜索范围迅速减小直到只剩下一个单词。
仅当列表是有序的时候二分查找才适用。例如电话簿中的名字按字母顺序排列因此可以使用二分查找来查找名字。
运行时间
让我们再次回到二分查找。使用二分查找相比于简单查找能节省多少时间呢简单查找是逐个地检查数字如果列表包含 100 个数字最多需要猜测 100 次。而如果列表包含 40 亿个数字最多需要猜测 40 亿次。换句话说最多需要的猜测次数与列表的长度相同这种情况被称为线性时间linear time。
然而二分查找则不同。如果列表包含 100 个元素最多只需猜测 7 次如果列表包含 40 亿个数字最多只需猜测 32 次。相比之下二分查找的运行时间是对数时间logarithmic time。
下表总结了我们所发现的情况
总结
当我们进一步探讨二分查找和简单查找之间的差异时不难发现二分查找的性能优势随着元素数量的增加变得更加显著。虽然在开始时二分查找的速度提升可能并不明显但随着列表规模的增长它的优越性将愈发凸显出来。
简单查找以线性时间的方式进行每增加一个元素它需要的额外时间也会线性增长。这就导致当元素数量庞大时每次查找都会变得耗时且不实际。例如如果你有一个拥有数百万个元素的数据集使用简单查找进行查询可能会变得极其缓慢甚至不切实际。然而二分查找以对数时间的方式运作每次查找只需要排除一半的元素。
这意味着尽管数据量增加每次查找所需的额外时间增长得非常缓慢。就像是在探索一个迷宫时你只需每次选择一个正确的路径逐渐逼近目标而不是逐一检查所有可能的路径。
这种对数级别的优越性意味着在大数据集或者长列表中二分查找的速度几乎不会受到影响。它的查询速度可以在常数时间内保持无论数据规模如何增长。而这也是为什么在现代计算机科学中二分查找是一种备受推崇的高效算法。
因此无论是在简单的名字查找、大规模数据处理还是搜索庞大的字典中的单词二分查找都是一种强大的工具能够在海量信息中快速找到目标。在信息爆炸的今天掌握并充分利用这种高效的算法对于优化搜索效率、提升数据处理速度至关重要。
代码示例
Python
def binary_search(lst, item):left 0right len(lst) - 1while left right:# 你每次都检查中间的元素。mid (left right) // 2val lst[mid]if val item:return midif val item:# 如果猜的数字大了就修改rightright mid - 1else:# 如果猜的数字小了就相应地修改left。left mid 1return -1 # Return -1 if item is not foundmy_list [1, 2, 3, 4, 5, 6, 7, 8]print(binary_search(my_list, 6))Java
public class BinarySearch {public static int binarySearch(int[] arr, int target) {int left 0;int right arr.length - 1;while (left right) {int mid (left right) / 2;int val arr[mid];if (val target) {return mid;}if (val target) {right mid - 1;} else {left mid 1;}}return -1;}public static void main(String[] args) {int[] myArray {1, 2, 3, 4, 5, 6, 7, 8};int searchItem 6;int result binarySearch(myArray, searchItem);System.out.println(result);}
}
