二分查找之【带权重的随机散布】

1. 在给Unity开发Scatter功能时，需基于每个prim的area占比，对单次散布到某个prim的概率进行加权，以达到平均散布的效果。

2. 于是问题变成了”提供一个随机数n（范围0~1），和由若干个prim的area构成的总区间，快速查找n所位于的子区间的ID (就是prim ID) "，且显而易见的是，使用二分查找效率最高。

1. 该方法适用于所有带权重的随机映射，比如排布A、B、C三个资产时，想让其分布比例为3：2：1，就可以用该思路。

using UnityEngine;
using Random=System.Random;

List<Vector2> BuildInterval(List<float> areas, float totalArea) //通过每个prim的面积占比，来构建一个0-1的总区间
{
    List<Vector2> intervals = new List<Vector2>();
    float left = 0f, right = 0f;
    foreach (float area in areas) {
        Vector2 interval = new Vector2();
        right = left + area / totalArea;
        interval.x = left;
        interval.y = right;
        intervals.Add(interval);
        left = right;
    }
    return intervals;   //该List的顺序是正序的
}

int FindInterval(List<Vector2> intervals, float n)  //返回所在区间号，区间号实际就是prim的ID
{
    int low = 0, high = intervals.Count - 1;
    while (low<= high)
    {
        int mid = (low + high) / 2;
        if (n <= intervals[mid].y)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;     
}

int main()
{
	List<float> areas = {1.0f, 2.22f, 3f, 4.5f, 5.3f, 6.82f};
	float totalArea = areas.Sum(area => area);

	List<Vector2> intervals = BuildInterval(areas, totalArea);
  Random rand = new Random();
	int inInterval = FindInterval(intervals , (float)rand.NextDouble()); //返回的值实际就是prim id
}