擅长:python、mysql、java
<p>要检查每个保留元素是否在阈值的两个元素之间,可以使用对分(即每次检查的日志(n)时间)</p>
<p><strong>代码</strong></p>
<pre><code>from bisect import bisect_left
def binary_search(a, x):
"""Index of where x would be inserted into a
return None if x < min(a) or x > max(a)"""
i = bisect_left(a, x)
return i if i != len(a) and i > 0 else None
threshold = [0.123,0.108,0.102,0.087]
threshold_asc = threshold[::-1]
retention = [0.123, 0.19,1,0.57,5,0.09, 0.087]
for r in retention:
print(f'{r} ->> {binary_search(threshold_asc, r)}')
</code></pre>
<p><strong>输出</strong></p>
<pre><code>0.123 ->> 3
0.19 ->> None
1 ->> None
0.57 ->> None
5 ->> None
0.09 ->> 1
0.087 ->> None
</code></pre>
<p><strong>复杂性</strong></p>
<blockquote>
<p>O(log(N)) for each check of retention. This is more efficient than
walking the list of thresholds to find pairs of surrounding values which would be O(N).</p>
</blockquote>