马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 yanghongchen666 于 2022-9-29 14:51 编辑
二分查找(特点):
1.有序的元素列表
2.如果改元素包含在该列表，返回其元素位置; 否则返回null
3.对于n个元素的列表使用二分查找只需要log_2 n 步
举例:
如果有32个元素的列表查找最后一个元素
普通方法： 32次
二分算法: log_2 32 = 5 (2^5=32) 5步
#binary seacher
def binary_search(list,item):
#low和high用于跟踪要在其中查找的列表部分
low = 0 #列表起点
high = len(list) -1 #列表终点(因为列表长度会比元素多一个所以这里要减一)
while low <= high: #只要范围没有缩小到1一直循环
#每次检查中间元素
mid = int((low + high) / 2) #如果(mid+high)不是偶数, 如果遇到切片为小数的情况使用int()强制转换为整形
guess = list[mid]
#找到元素
if guess > item:
high = mid-1
#如果猜小了 low的值往上增加
elif guess < item:
low = mid+1
#如果猜大了 high的值往下减去
else:
return mid
return None #没有指定元素
课后问题:
1.1 假设有一个包含128个名字的有序列表，你要使用二分查找在其中
查找一个名字，请 问最多需要几步才能找到？
1.2 上面列表的长度翻倍后，最多需要几步？
log_2 256 = 8 一共需要8步才能找到一个列表包含128个元素其中之一的元素
1.3 一个列表为[-1,0,3,5,9,12]这样的数组使用二分查找找到9这个数字的位置
]1.3 请从数组[-1,0,3,5,9,12]中使用二分查找算法找到9这个元素的位置
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-9-29 14:50:02
置顶卡
千斤顶
显身卡
楼主
发表于 2022-9-30 13:27:52
