Select randomly by weight [prefix and + dichotomy + random target]

Preface

Where there is order, there is dichotomy , In particular, the array elements are all larger than 0 Prefix and array , Two points is a sharp weapon .

One 、 Choose randomly by weight

Two 、 The prefix and + Two points + Random target

package everyday.medium;

import java.util.Arrays;
import java.util.Random;

//  Choose randomly by weight 
public class PickIndex {
    
    /*  Give an array of weights w, Select randomly by weight .  Direct prefix and  +  Random integers  +  Two points search  ==  return idx, Just get the subscript . */
    public PickIndex(int[] w) {
    
        prefix = new int[w.length];
        //  Assign values to prefixes and .
        int sum = 0, idx = 0;
        for (int i : w) prefix[idx++] = (sum += i);
        System.out.println(Arrays.toString(prefix));
    }

    int[] prefix;
    Random rand = new Random(1);

    public int pickIndex() {
    
        //  Random integer 
        // bug1: If each time is random feed Are all the same , It produces the same number .
        // Random rand = new Random(System.currentTimeMillis());
        // rand.nextInt(n) Range [0,n)
        int target = rand.nextInt(prefix[prefix.length - 1]);
        //  Binary search position in prefix and .
        return binarySearch(target + 1);
    }

    //  Find a comparison target  A place just big or equal to .
    private int binarySearch(int target) {
    
        int low = 0, high = prefix.length - 1;

        while (low < high) {
    
            int mid = low + (high - low >>> 1);
            int midVal = prefix[mid];

            if (midVal < target) low = mid + 1;
            else if (midVal > target) high = mid;// You can't subtract one , Because I went to the right , I can't go back . Coordinate to remove the integer to approximate .
            else return mid;
        }
        return high;
    }

    public static void main(String[] args) {
    
        for (int i = 0; i < 20; i++) {
    
            Random rand = new Random(1);

            System.out.println(rand.nextInt(100));
        }
    }
}

summary

1） Ordered array / Positive prefix and And The close connection of dichotomy .

reference

[1] LeetCode Choose randomly by weight