python – 如何有效地在大型排序数组中找到最接近另一个值X的值

发布时间：2020-12-20 11:50:42 所属栏目：Python 来源：网络整理

导读：对于排序列表,如何找到接近给定数字的最小数字？例如, mysortedList = [37,72,235,645,715,767,847,905,908,960] 如何快速找到小于或等于700的最大元素？ (如果我有1000万个元素,那么线性搜索会很慢).在这个例子中,答案是645. 解决方法您可以使用 bisect

对于排序列表,如何找到接近给定数字的最小数字？

例如,

mysortedList = [37,72,235,645,715,767,847,905,908,960]

如何快速找到小于或等于700的最大元素？ (如果我有1000万个元素,那么线性搜索会很慢).在这个例子中,答案是645.

解决方法

您可以使用 bisect模块：

import bisect

data = [37,960]

location = bisect.bisect_left(data,700)

result = data[location - 1]

这是标准库中的一个模块,它将使用binary search来查找所需的结果.根据您需要的确切值,您也可以使用bisect_right而不是bisect_left.

这比迭代列表更快,因为二进制搜索算法可以跳过不包含答案的部分数据.这使得它非常适合在已知数据被排序时找到最接近的数字.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!