202406281435
tags: #binary-search

var Solution = function(w) {
	this.wSums = [...w];
	for (let i = 1; i < w.length; i++) {
		this.wSums[i] += this.wSums[i - 1];
	}
};

Solution.prototype.pickIndex = function() {
	const n = this.wSums.length;
	const randomIdx = Math.floor(Math.random() * this.wSums[n - 1]) + 1;
	let start = 0;
	let end = n;
	while (start <= end) {
		const mid = Math.floor((end - start) / 2) + start;
		if (this.wSums[mid] === randomIdx) {
			return mid;
		}
		else if (this.wSums[mid] < randomIdx) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}
	return end + 1;
};

Reference

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