首页 > 代码库 > 练习-二分查找
练习-二分查找
# 在有序序列内查找,判断大于还是小于中间值,每次搜索减一半,直到达到退出条件 # 递归二分查找具体索引 def search(num, start, end, args): global m m += 1 middle = (start + end) // 2 # 整除取中间值 # print(‘start:%s , end:%s , middle:%s , args[middle]:%s‘ % ( # start, end, middle, args[middle])) if num == args[middle]: # 判断是否匹配 return middle,m # 返回匹配索引 elif end == middle: # start == end or return ‘未找到该值‘,m elif num > args[middle]: # 判断所找值是否大于序列中间的值 # 在上面已经判断过了中间索引,所以下次要从中间索引+1位置开始,否则容易出现死循环 start = middle + 1 return search(num, start, end, args) # 继承上层的结束索引,改变开始索引 else: # 小于序列中间值 # 在上面已经判断过了中间索引,所以下次要从中间索引-1位置开始,否则容易出现死循环 end = middle - 1 return search(num, start, end, args) # 继承上层的开始索引,改变结束索引 # 循环二分查找索引,返回索引和次数 def search2(num, args): start = 0 # 首索引 end = len(args) - 1 # 尾索引 middle = (start + end) // 2 m = 0 while num != args[middle]: # 不等于就继续找 m += 1 if end == middle: return ‘未找到 %s‘ % num, m elif num > args[middle]: start = middle + 1 else: end = middle - 1 middle = (start + end) // 2 else: return middle, m lis = list(range(1, 10100002, 4)) m = 0 # 计次 num = 10100001 # 查找值 if num <= lis[len(lis) - 1]: # print(lis) # ret = search(num, 0, len(lis) - 1, lis) # print(‘查找值: %s ,索引: %s ,共找了: %s 次‘ % (num, ret, m)) ret = search(num-4, 0, len(lis), lis) print(‘查找值: %s ,索引: %s ,共找了: %d 次‘ % (num-4, *ret)) ret = search2(num, lis) print(‘查找值: %s ,索引: %s ,共找了: %d 次‘ % (num, *ret)) else: print(‘数字超过范围‘) # 递归切片二分查找是否存在序列里 def search3(num, nums): middle = len(nums) // 2 if len(nums) < 1: # 序列为空说明找完了 return False if num == nums[middle]: return True elif num > nums[middle]: return search3(num, nums[middle + 1:]) else: return search3(num, nums[:middle]) # 切片结束位置是middle的前一个位置,所以不用再减一 # 循环切片二分查找是否存在序列里 def search4(num, nums): while len(nums) > 0: middle = len(nums) // 2 if num == nums[middle]: return True elif num > nums[middle]: nums = nums[middle + 1:] else: nums = nums[:middle] # 切片结束位置是middle的前一个位置,所以不用再减一 else: return False lis = list(range(1, 10100002, 4)) print(search3(2, lis)) print(search4(10100001, lis))
练习-二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。