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

Question

我最近接受了一次采访，采访者给了我以下场景，并问我将使用什么数据结构来实现它：

你有100个大理石，每个大理石是红色、蓝色或绿色。这些大理石被扔进一个袋子里，你需要有一些机制来取回一个随机的彩色大理石（带有替换品）。

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

这个解决方案很好，但他问：“如果你有很多不同的颜色，每种颜色都有不同的颜色，那会怎么样？”

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

Answer 1

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

Answer 2

诀窍在于，你看的是二进制搜索结束的索引，而不是那个位置的值。我还不知道这个算法。谢谢你的描述。我用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]