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

pionrrt

想问一下，mid=(low + high)这里为什么不除以2呢，我 输入 mid=(low + high)/2再运行代码就是错的

最佳答案

月排行榜 / 总排行榜

isdkz

2023-6-7 14:32:03

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

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

修正后的代码如下：

1. def binary_search(list, item):
   
2.     low = 0
   
3.     high=len(list)-1
   
4. 
   
5.     while low<=high:
   
6.         mid=(low + high)//2
   
7.         guess=list[mid]
   
8.         if guess==item:
   
9.             return mid
   
10.         if guess>item:
    
11.             high=mid-1
    
12.         else:
    
13.             low=mid+1
    
14.     return None
    
15. 
    
16. my_list=[1,3,5,7,9]
    
17. print(binary_search(my_list, 7))
    

复制代码

现在这个函数应该可以正常工作了。如果输入的item在列表中，函数将返回item的索引；如果item不在列表中，函数将返回None。

跳转到最佳答案楼层

isdkz

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

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

修正后的代码如下：

1. def binary_search(list, item):
   
2.     low = 0
   
3.     high=len(list)-1
   
4. 
   
5.     while low<=high:
   
6.         mid=(low + high)//2
   
7.         guess=list[mid]
   
8.         if guess==item:
   
9.             return mid
   
10.         if guess>item:
    
11.             high=mid-1
    
12.         else:
    
13.             low=mid+1
    
14.     return None
    
15. 
    
16. my_list=[1,3,5,7,9]
    
17. print(binary_search(my_list, 7))
    

复制代码

现在这个函数应该可以正常工作了。如果输入的item在列表中，函数将返回item的索引；如果item不在列表中，函数将返回None。

pionrrt

那为啥不用地板除//, 光写成这样mid=(low + high)也能行呢

pionrrt

isdkz 发表于 2023-6-7 14:32
在这个二分查找的算法中，你需要计算中间索引，这个索引应该是low和high索引的平均值，所以应该除以2。但是 ...

那为啥不用地板除//, 光写成这样mid=(low + high)也能行呢

isdkz

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)  也能行，可能只是因为这种情况下恰好得到了正确的结果，但这并不代表这种写法是正确的。

pionrrt

isdkz 发表于 2023-6-7 15:09
实际上，这样写  mid=(low + high)  是错误的。这不是计算low和high的平均值（也就是中间值），而只是简 ...

嗯 好的，谢谢！