二分查找算法概括
发布时间：2021-11-15 11:49:34 所属栏目：PHP教程 来源：互联网
导读：问题引入 假设我们要从一个电话簿中查找一个以L打头的人，可以从头开始翻页，直接进入L打头的部分。但我们可能不这么做，我们可能从中间开始，因为我们知道以L打头的名字在电话簿的中间；再假设我们从字典中查找一个以字母O打头的单词，我们也将从中间开始查
|
问题引入 假设我们要从一个电话簿中查找一个以L打头的人，可以从头开始翻页，直接进入L打头的部分。但我们可能不这么做，我们可能从中间开始，因为我们知道以L打头的名字在电话簿的中间；再假设我们从字典中查找一个以字母O打头的单词，我们也将从中间开始查找。 如果现在假设你要登录Facebook，当你这样做的时候，Facebook必须核实你的是否具有该网站的注册账户信息，因此他会从数据库中查找你的用户名，假设你的用户名为sunyboy，Facebook可以以A打头开始查找，更合乎逻辑的做法是从中间开始查找。 这是一个查找的问题，在上述所有请情况下，都可以使用同一种算法来解决问题，这种算法是二分查找。 概念 二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置，否则返回null。 基本原理 通过一个实例来说明二分查找的原理； 你随便想一个1~100的数字，我的目标是以最少的次数猜到该数字。我每次猜测之后，你会说小了、大了或对了。 假设我从1开始猜测，这样一个一个数字猜测，每次猜测都只能排除一个数字。如果你想的数字是99，我得猜测99次才能猜到！这是简单查找，更准确的说法就是傻找； 最佳的方法是从这个数字1~100之间取中间数，这样就可以排除一半的数字！我知道1~50都小了，我会去猜测75，你说数字大了，我会去猜测63，你说大了，我会猜测57，这就猜对了；这种查找方法会在7次内猜测出答案，这个7又是如何得来的呢？ 一般而言，对于包含n个元素的列表，用而二分查找最多需要log2n（对数：例：2^3=8 <-> log28=3 ）步，而简答查找最多需要n步； 代码示例 __Author__ = "ZhiChao Ma" #versions:Python3.5.2 #使用二分查找法快速从一个数组中查找一个指定元素，并返回该元素的索引值 def binary_search(list, item): #low和high用于跟踪要在其中查找的列表部分 low = 0 high = len(list)-1 while low <= high: #只要范围没有缩小到只包含一个元素 #如果(low + high)不是偶数，python自动向下取整，这里来检查中间元素 mid = (low + high) guess = list[mid] if guess == item: #找到了元素 return mid if guess > item: #猜的数字大了 high = mid -1 else: #猜的数字小了 low = mid + 1 return None #没有指定元素 my_list1 = ['zhangsan', 'lisi', 'wangwu',] my_list2 = list(range(10000)) print(binary_search(my_list1, 'lisi')) print(binary_search(my_list2, 5002)) print(binary_search(my_list2, -110)) 输出结果： 1 5002 None  （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号