Python通过二分查找，查询有序列表中元素的下标
为什么使用二分查找？
因为二分查找可以快速的查找一个有序列表中的元素注意：查找的对象必须是一个有序的列表！！！！
代码示例
通过while循环的方式可以查询出对应的下标，元素不存在在列表中返回-1，就相当于手动给python列表实现了String（字符串）的find方法。
（注：代码是在下花了四个小时绞尽脑汁才想出来的，肯定还是有不足的地方，比如每次循环都要判断right-left==1）
def BinarySearch(item, list):'''二分查找有序列表中的元素:param item: 需要查找的元素:param list: 列表:return: 查找到返回元素在list中的下标，反之返回-1'''end_time = False # 结束时间left = 0 # 左下标，初始值为0right = len(list) # 右下标，初始值为列表的长度while left < right:if right - left == 1: # 判断是否在做最后一次运算 right - left == 1 表示已经开始进行最后一个元素的判断if end_time == True:return -1 # 没有查找到返回-1end_time = True # 将end_time改成True,标志着已经开始了最后一次的查找mid_site = (left + right) // 2if item == list[mid_site]:return mid_site # 查找到返回对应下标elif item > list[mid_site]:left = mid_site # 如果当前元素大于列表中mid_site下标对应的值，就将mid_site赋值给leftelse:right = mid_site # 如果当前元素小于列表中mid_site下标对应的值，就将mid_site赋值给rightif __name__ == '__main__':list01 = [1, 2, 4, 6, 7, 9, 10, 11, 13]result01 = BinarySearch(10, list01)print(result01) # 6 ==> 表示10在list01中的下标为6result02 = BinarySearch(1000, list01)print(result02) # -1 ==> 表示3在list01中查找不到
通过递归的方式–目前本人只实现了判断元素是否在列表中，还没有找到有效的替代方法去替换while循环中的left和right两个变量（有那位大佬想到办法了可以再评论里发表想法）
def BinarySearch(item, list):'''二分查找有序列表中的元素:param item: 需要查找的元素:param list: 列表:return: 查找到返回True，反之查找不到返回False'''# 获取列表的长度赋值给list_lengthlist_length = len(list)# 判断列表的长度是否大于0if list_length > 0:# 计算列表中间位置mid_site = list_length // 2if item == list[mid_site]: # 判断列表中中间位置是否和需要查找的元素相等return True # 查找到返回Trueelif item > list[mid_site]: # 如果需要查找的元素大于列表中间的元素# 继续在列表的后半段中查找该元素# 注意：因为中间位置的元素在上面已经计算过一次，为避免重复的运算# 这里需要去除mid_site对应的return BinarySearch(item, list[mid_site + 1:])else: # 如果需要查找的元素小于列表中间的元素# 在列表的前半段中查找该元素# 因为列表的切片并不包含结尾的元素，所以这里不需要减一return BinarySearch(item, list[:mid_site])else:return False # 如果查找不到，返回Falseif __name__ == '__main__':list01 = [1, 2, 4, 6, 7, 9, 10, 11, 13]result01 = BinarySearch(9, list01)print(result01)result02 = BinarySearch(12, list01)print(result02)
如果觉得《Python通过二分查找 查询有序列表中元素的下标》对你有帮助，请点赞、收藏，并留下你的观点哦！
