Python3: 二分法查找的两种实现方法

joseph · · 49 次点击 · 开始浏览    置顶
二分法查找是一种基础的、简单而高效的算法,又称为折半查找。顾名思义,就是将待查表一分为二,从而减少了查找次数,提高了效率。但缺点就是待查表必须为顺序表,并且待查表在查找时不宜做增删操作。 其最优时间复杂度为O(1),最坏时间复杂度为O(logn)。代码样例: ``` # coding:utf-8 方法一:递归法 def binarySearch_01(listx, item): """Be of recursion""" length = len(listx) if length > 0: #定义中间值下标: split = length // 2 if listx[split] == item: return True elif listx[split] > item: return binarySearch_01(listx[:split], item) else: return binarySearch_01(listx[split+1:], item) return False 方法二:非递归法 def binarySearch_02(listx, item): """Not be of recursion""" length = len(listx) start = 0 #待查表起始元素下标 end = length-1 #待查表终止元素下标 while start <= end: #定义中间值下标: split = (start + end) // 2 if item == listx[split]: return True elif item < list[split]: end = split-1 else: start = split+1 return False #功能测试: if __name__ == "__main__": list = [-300, -10, 2, 23, 29, 58, 59, 102, 201, 268] print(binarySearch_01(list, 102)) print(binarySearch_01(list, 200)) print(binarySearch_02(list, 102)) print(binarySearch_02(list, 200)) ```

关注本站微信公众号(和以上内容无关)Debiancn ,扫码关注:DebianCN

49 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传