鱼C论坛

 找回密码
 立即注册
查看: 1878|回复: 5

[已解决]mid=(low + high)这里为什么不除以2呢

[复制链接]
发表于 2023-6-7 14:27:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
想问一下,mid=(low + high)这里为什么不除以2呢,我 输入 mid=(low + high)/2再运行代码就是错的
截图未命名.jpg
截图未命名.jpg
最佳答案
2023-6-7 14:32:03
本帖最后由 isdkz 于 2023-6-7 14:33 编辑

在这个二分查找的算法中,你需要计算中间索引,这个索引应该是low和high索引的平均值,所以应该除以2。但是在Python中,除法运算符"/"返回的是一个浮点数,这样可能会导致mid不再是整数,而在索引列表时,我们需要一个整数索引。所以,你应该使用"//"运算符,它会进行整数除法(也称为地板除),这样可以得到一个整数结果。

所以,你应该将  mid=(low + high)  修改为  mid=(low + high)//2 。

修正后的代码如下:
def binary_search(list, item):
    low = 0
    high=len(list)-1

    while low<=high:
        mid=(low + high)//2
        guess=list[mid]
        if guess==item:
            return mid
        if guess>item:
            high=mid-1
        else:
            low=mid+1
    return None

my_list=[1,3,5,7,9]
print(binary_search(my_list, 7))

现在这个函数应该可以正常工作了。如果输入的item在列表中,函数将返回item的索引;如果item不在列表中,函数将返回None。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-6-7 14:32:03 | 显示全部楼层    本楼为最佳答案   
本帖最后由 isdkz 于 2023-6-7 14:33 编辑

在这个二分查找的算法中,你需要计算中间索引,这个索引应该是low和high索引的平均值,所以应该除以2。但是在Python中,除法运算符"/"返回的是一个浮点数,这样可能会导致mid不再是整数,而在索引列表时,我们需要一个整数索引。所以,你应该使用"//"运算符,它会进行整数除法(也称为地板除),这样可以得到一个整数结果。

所以,你应该将  mid=(low + high)  修改为  mid=(low + high)//2 。

修正后的代码如下:
def binary_search(list, item):
    low = 0
    high=len(list)-1

    while low<=high:
        mid=(low + high)//2
        guess=list[mid]
        if guess==item:
            return mid
        if guess>item:
            high=mid-1
        else:
            low=mid+1
    return None

my_list=[1,3,5,7,9]
print(binary_search(my_list, 7))

现在这个函数应该可以正常工作了。如果输入的item在列表中,函数将返回item的索引;如果item不在列表中,函数将返回None。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-6-7 14:43:33 | 显示全部楼层
那为啥不用地板除//, 光写成这样mid=(low + high)也能行呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-6-7 14:44:07 | 显示全部楼层
isdkz 发表于 2023-6-7 14:32
在这个二分查找的算法中,你需要计算中间索引,这个索引应该是low和high索引的平均值,所以应该除以2。但是 ...


那为啥不用地板除//, 光写成这样mid=(low + high)也能行呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-6-7 15:09:26 | 显示全部楼层
pionrrt 发表于 2023-6-7 14:44
那为啥不用地板除//, 光写成这样mid=(low + high)也能行呢

实际上,这样写  mid=(low + high)  是错误的。这不是计算low和high的平均值(也就是中间值),而只是简单地将low和high相加。在二分查找算法中,我们应该找到low和high的平均值来得到中间索引,所以我们应该使用  mid=(low + high)//2 。

如果只是  mid=(low + high) ,在某些情况下可能会导致错误或者查找效率低下,因为这并没有真正地将查找范围减半。

所以,正确的写法应该是  mid=(low + high)//2 。如果你在某些情况下看到  mid=(low + high)  也能行,可能只是因为这种情况下恰好得到了正确的结果,但这并不代表这种写法是正确的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2023-6-7 16:55:38 | 显示全部楼层
isdkz 发表于 2023-6-7 15:09
实际上,这样写  mid=(low + high)  是错误的。这不是计算low和high的平均值(也就是中间值),而只是简 ...

嗯 好的,谢谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-27 10:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表