python实现二分法
2024-09-03 09:49:55
前言:
二分法主要是用来查找位置的id,每次能够排除掉一半的数据,查找的效率非常高,但是局限性比较大。 必须是有序序列才可以使用二分查找。
原理
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
代码如下:
# encoding:utf-8
def BinarSearch(lst,value):
"""
python 实现二分查找
"""
first = 0
last = len(lst)-1
while first < last:
mid_value = int((first+last)//2)
if lst[mid_value] < value:
first = mid_value +1
elif lst[mid_value] > value:
last = mid_value - 1
else:
return mid_value
return False
if __name__ == '__main__':
lst = [1, 3, 4, 8, 22, 65, 73]
print(lst)
index = BinarSearch(lst, 8)
print(index)
最新文章
- 超详细Web前端开发规范文档
- IOS开发札记(2015-08-20)
- HTTP超文本传输协议-HTTP/1.1中文版
- css3样式二
- MongoDB 概念解析
- Git fork指令
- css3滚动提示
- 写一个jq插件
- iOS6与iOS7屏幕适配技巧
- 如何管理安卓android手机下google(谷歌)的通讯录联系人账户
- 常见类——Object
- 恶补web之二:css知识(1)
- angular1.0 app
- 加载更多的ajax 字符串拼接
- NOIP2016原题终结测试(2017081801)
- 生产者消费者模型——wait/notify/notifyAll使用
- webpack快速入门——集中拷贝静态资源
- 【Java】数组使用
- linux、WINDOWS命令行下查找和统计行数
- Mysql解压版配置环境等
热门文章
- C#操作Word的超详细总结 ---转载
- java list 清空列表所有元素
- in comment after two dashes (--) next character must be >; not - (position: START_TAG seen ...
- redis集群命令及常规操作
- 若块级元素被设置为 display: table-cell 便无法设置宽度
- keep-alive的使用
- alerm和pause
- CSS盒模型的组成部分及实际大小
- 回文串[APIO2014](回文树)
- Linux中{ }的用法