一个二分查找的小问题--由python四舍五入引起

harriszh 发布于2019-07-31 10:25 / 1178人阅读

摘要：出现这个问题原因就处在这个取整的操作他不是我们理解的四舍五入，而是简单的截取整数部分。上面的例子修改为运行后输出为所以上面的二分查找也就可以修改成为了实现四舍五入加上一个这样解决了二分查找中的这个小问题。

在看算法图解的过程了解到了很多算法的知识，但在中间也遇到了一个小问题。
下面我们就看一下这个小问题时怎么解决的。
下面是书中的源码：

def binary_search(list, item):
    low =  0
    high = len(list)
    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

当我们用下面的数据运行时:

list = [1, 2, 3, 4, 5]
item = 3
position = binary_search(list, item)
print(position)

会导致如下错误：

Traceback (most recent call last):
  File "binary_search.py", line 17, in 
    position = binary_search(list, item)
  File "binary_search.py", line 6, in binary_search
    guess = list[mid]
TypeError: list indices must be integers or slices, not float

上面信息的意思是索引类型错误，索引必须为整型而不是float型。
这是因为python中除法即“/”会自动转换类型。将无法整除的数字转换成浮点型。
下面是我一开始想到的解决办法：

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # 将结果加一个类型转换即可
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

但当使用下面的数据进行测试时：

list = [1, 2, 3, 4, 5]
item = 5
position = binary_search(list, item)
print(position)

结果就是循环不会停止了。
为了找到问题出在哪里。我们在循环体中加一个pirnt语句输出一下mid

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)  # 将结果加一个类型转换即可
        print(mid)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

还是使用上面的数据运行一下。
可以在终端中看到一直在循环输出3。
出现这个问题原因就处在int() 这个取整的操作他不是我们理解的四舍五入，而是简单的截取整数部分。
看下面的例子。

a = 5.4
b = 5.5
c = 5.6
print(int(a))
print(int(b))
print(int(c))

运行后输出为：

5
5
5

为了解决这个问题我们只需要给要取整的数加一个0.5即可。
上面的例子修改为：

a = 5.4
b = 5.5
c = 5.6
print(int(a + 0.5))
print(int(b + 0.5))
print(int(c + 0.5))

运行后输出为：

5
6
6

所以上面的二分查找也就可以修改成：

def binary_search(list, item):
    low =  0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2 + 0.5)  # 为了实现四舍五入加上一个0.5
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid - 1
    return None

这样解决了二分查找中的这个小问题。

GPU云服务器云服务器二分查找二分查找代码二分法查找二分查找c语言实例

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43798.html

Python基础之(一)基本数据类型

摘要：但是在转化中，浮点数转化为二进制后，不会精确等于十进制的。一般情况下，只要简单地将最终显示的结果用四舍五入到所期望的十进制位数，就会得到期望的最终结果。四舍五入内建函数。在中的第二个数，表示要保留的小数位数，返回值是一个四舍五入之后的数值。数字基本类型首先，进入Python交互模式中： //整数 >>> 3 3 //长整数 >>> 3333333333333333333333...

yagami 2019-07-25 10:50 评论0 收藏0
学Python说简单真的简单，说难也难，就由过来人给你总结为什么吧。

摘要：数据科学其实就是机器学习，数据分析和数据可视化。机器学习通过实现算法，该算法能够自动检测输入中的模式。一般应用于人脸识别语音识别热门机器学习算法包括神经网络深度学习支持向量机随机森林进行数据分析可视化进行数据可视化时，是非常热门的库。 ...

HtmlCssJs 2021-11-11 16:55 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

zsirfs 2019-08-23 15:33 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

you_De 2019-08-16 15:26 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

gotham 2019-07-31 10:07 评论0 收藏0