Entwerfen Sie einen schnellen Algorithmus zum wiederholten Generieren von Zahlen aus der diskreten Verteilung: Wenn ein Array a [] nicht negativer reeller Zahlen mit der Summe 1 erstellt wird, besteht das Ziel darin, den Index i mit der Wahrscheinlichkeit a [i] zurückzugeben.

Diese Frage fand ich in einem Online-Algorithmusbuch, Einführung in die Programmierung in Java, Kapitel 4.2: Sortieren und Suchen (http://introcs.cs.princeton.edu/java/42sort/).

der Hinweis sagt:

Bilden Sie ein Array s [] von kumulierten Summen, so dass s [i] die Summe der ersten i Elemente von a [] ist. Erzeugen Sie nun eine zufällige reelle Zahl r zwischen 0 und 1 und geben Sie mit der binären Suche den Index i zurück, für den s [i] ≤ s [i + 1] ist.

Einige, wie ich nicht in der Lage bin, den Hinweis zu verstehen und daher nicht die Lösung zu finden.