CODEWITHSUNDEEP
calgorithmrandom
Walt
Walt

Reputation: 1426

Random number generator in arbitrary probability distribution fashion

HERE is the geeksforgeeks solution. I am not able to understand the findCeil() part. Step 4. Find index of Ceil of random number generated in step #3 in the prefix array. Let the index be indexc.

// Utility function to find ceiling of r in arr[l..h]
int findCeil(int arr[], int r, int l, int h)
{
    int mid;
    while (l < h)
    {
         mid = l + ((h - l) >> 1);  // Same as mid = (l+h)/2
        (r > arr[mid]) ? (l = mid + 1) : (h = mid);
    }
    return (arr[l] >= r) ? l : -1;
}

Can someone please explain what is being done.

Upvotes: 0

Views: 586

Answers (1)

Katie
Katie

Reputation: 1270

It's performing a binary search of the array to find the first element of the array with a value greater than r. The wiki article should explain the technique pretty well.

edit: Here's an animation of an example search

Upvotes: 1

Related Questions