528 random pick with weight

https://leetcode.com/problems/random-pick-with-weight/

class Solution {
    int[] array;
    double[] probs;
    double[] prefixes;
    public Solution(int[] w) {
        array = w;
        int sum = 0;
        for (int num : w) {
            sum += num;
        }
        double prob = 0;
        probs = new double[w.length];
        prefixes = new double[w.length];
        for (int i = 0; i < w.length; i++) {
            probs[i] = (double)w[i] / sum;
            prob += probs[i];
            prefixes[i] = prob;
        }
    }
    
    public int pickIndex() {
        Random random = new Random();
        double val = random.nextDouble();
        int lo = 0;
        int hi = array.length - 1;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefixes[mid] < val) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */

tricky的地方在于看出来什么地方用binary search最合适

感觉搜索范围的话用lo + 1 < hi好像不太适合？用lo < hi好像更好一点，感觉核心思想就是下一次搜索需不需要包括mid，而这跟搜索区间的开闭有关系，我们这里两边都是闭区间，因此如果mid处不可能就要排除掉，以及终止条件是左右两边相等，相当于收缩到了一个值