如何有效地在大型排序数组中找到最接近另一个值 X 的值 [英] How to find a value closest to another value X in a large sorted array efficiently

问题描述

对于已排序的列表，如何找到与给定数字相近的最小数字?

For a sorted list, how can I find the smallest number which close to the a given number?

例如

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

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

How can I find the largest element which is less or equal to 700 quickly? (If I have 10 million elements, then it will be slow to search linearly). In this example, the answer is 645.

推荐答案

您可以使用 bisect 模块:

You can use the bisect module:

import bisect

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

location = bisect.bisect_left(data, 700)

result = data[location - 1]

这是标准库中的一个模块，它将使用二进制搜索来查找所需的结果.根据您需要的确切值，您还可以使用 bisect_right 而不是 bisect_left.

This is a module in the standard library which will use binary search to find the desired result. Depending on the exact value that you need you can also use bisect_right instead of bisect_left.

这比遍历列表更快，因为二分搜索算法可以跳过不包含答案的部分数据.这使得它非常适合在已知数据已排序的情况下寻找最接近的数字.

This is faster than iterating over the list because the binary search algorithm can skip parts of the data that won't contain the answer. This makes it very suitable for finding the nearest number when the data is known to be sorted.

这篇关于如何有效地在大型排序数组中找到最接近另一个值 X 的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！