A Single-Pass Solution

Although this code works, it is not as efficient as it could be. Every time it invokes inBucket, it traverses the entire array. As the number of buckets increases, that gets to be a lot of traversals.

It would be better to make a single pass through the array, and for each value, compute which bucket it falls in. Then we could increment the appropriate counter.

In the previous section, we took an index, i, and multiplied it by the bucketWidth in order to find the lower bound of a given bucket. Now we want to take a value in the range 0.0 to 1.0, and find the index of the bucket where it falls.

Since this problem is the inverse of the previous problem we might guess that we should divide by the bucketwidth instead of multiplying. That guess is correct.

Remember that since bucketWidth = 1.0 / numBuckets, dividing by bucketWidth is the same as multiplying by numBuckets. If we take a number in the range 0.0 to 1.0 and multiply by numBuckets, we get a number in the range from 0.0 to numBuckets. If we round that number to the next lower integer, we get exactly what we are looking for---the index of the appropriate bucket.

Here I am using a typecast to round the value down to the next integer and convert it to type int at the same time.

Is it possible for this calculation to produce an index that is out of range (either negative or greater than a.length-1)? If so, how would you fix it?

An array like buckets, that contains counts of the number of values in each range, is called a histogram. As an exercise, write a method called histogram that takes an array and a number of buckets as parameters, and that returns a histogram with the given number of buckets.