python: 在浮点数组范围内查找值

Question

我有以下排序的 python 列表，尽管可能出现多个值：

[0.0943200769115388, 0.17380131294164516, 0.4063245853719435, 
 0.45796523225774904, 0.5040225609708342, 0.5229351852840304, 
 0.6145136350368882, 0.6220712583558284, 0.7190096076050408, 
 0.8486436998476048, 0.8957381707345986, 0.9774325873910711, 
 0.9832076130275351, 0.985386554764682, 1.0]

现在，我想知道特定值可能落在数组中的索引：

例如，值 0.25 会落在索引 2 中，因为它介于 0.173 和 0.40 之间。我想我可以通过列表并在 for 循环中执行此操作，但我想知道是否有更好的方法来执行此操作，这可能在计算上更有效率。我创建了这个数组一次，但必须执行多次查找。

Answer 1

如果您知道列表已经排序，那么教科书的解决方案是进行二分查找。您保留两个索引范围，最小值和最大值。将它们初始化为 0 和 len - 1。然后将 mid 设置为 (min + max) / 2。将索引 mid 处的值与您的目标值进行比较。如果它更小，则将 min 设置为 mid + 1。如果它更大，则将 max 设置为 mid - 1。重复直到找到该值或直到 max < min，在这种情况下，您将在 O( log(n)) 步骤。

Answer 2

>>> vals = [0.0943200769115388, 0.17380131294164516, 0.4063245853719435, 
 0.45796523225774904, 0.5040225609708342, 0.5229351852840304, 
 0.6145136350368882, 0.6220712583558284, 0.7190096076050408, 
 0.8486436998476048, 0.8957381707345986, 0.9774325873910711, 
 0.9832076130275351, 0.985386554764682, 1.0]

>>> import bisect
>>> bisect.bisect(vals, 0.25)
2

python: 在浮点数组范围内查找值

python: find value within range in float array

python

floating-point

intervals