二进制搜索-有人能清除这个面试算法吗？

Question

最近我进行了一次面试，面试官给了我以下场景，并问我将使用什么数据结构来实现它：

你有100个大理石，每个大理石要么是红色，要么是蓝色，或者是绿色。弹珠被扔进一个袋子，你需要有一些机制来回收一个随机颜色的大理石(与替换)。

好了放轻松点。在问了一些关于约束的问题后，我告诉他，我将使用一个简单的数组，其中每个桶代表一个大理石。随机数函数可以用来对数组进行索引，从而产生一个随机彩色大理石。

这个解决方案很好，但他接着问：“如果你有很多不同的颜色，每个颜色都有10亿<=的弹珠呢？”最初，我建议使用哈希表，其中每个键表示颜色，每个值表示该颜色中的弹珠数。采访者告诉我，这是一个很好的解决空间限制的方法，但现在产生n种颜色之一的可能性是1/n，而不是大理石总数给出的实际概率。我需要一些方法来保持概率不变，而不用将它们全部存储在内存中。最后我什么都没想，他给我的解决办法是：

找到每种颜色的总数(这将是O(n)，这对设置来说很好)，并设置一个数组，其中每个桶表示每种颜色的累积总数。例如，如果您的大理石总数为R: 3，B: 5，G: 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000。然后他说，你现在可以用一个带有随机索引的二进制搜索来获得一个随机颜色的大理石，同时保持正确的概率。有人能解释一下为什么会这样吗？这是否只是一个经过修改的二进制搜索，返回高于随机索引的第一个值？

Answer 1

诀窍是查看二进制搜索结束的索引，而不是该位置的值。我还不知道这个算法。谢谢你的描述。我在python中为您实现了它:)

import random
import bisect

# 10 red, 20 blue, 70 green
counts = [10, 20, 70]
sums   = [10, 30, 100]

# count how often some color occurs to verify later that the algorithm works correctly
bins = [0, 0, 0]
# randomly select 10000 colors
for _ in range(100000):
    random_index = random.randint(0, sums[-1]) # sums[-1] is the last value in array (100)
    # do binary search in sums array
    result = bisect.bisect_left(sums, random_index)
    bins[result] += 1

print(bins) # example output: [10875, 19732, 69393]

Answer 2

如果选择大理石颜色的随机指数介于1和N之间，那么得到特定颜色的概率是k/ N，其中k是分配给该颜色的数字数。你的面试官只是把颜色按顺序排列，这样每种颜色都有正确的数字k给它分配的指数(其中k是该颜色的原始弹珠的数目)，然后注意到给定一个介于1和N之间的随机指数，你可以进行二进搜索，找出随机指数所在的颜色的范围。假设1和N之间的随机指数是一致随机的，这将给出当有k个带有该颜色的弹珠时，得到颜色的正确概率k/N。