The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.


A good approach to problems like this is to think of simple methods that are easy to write, and that might turn out to be useful. Then you can combine them into a solution. Of course, it is not easy to know ahead of time which methods are likely to be useful, but as you gain experience you will have a better idea.

Also, it is not always obvious what sort of things are easy to write, but a good approach is to look for subproblems that fit a pattern you have seen before.

Back in Section 7.7 we looked at a loop that traversed a string and counted the number of times a given letter appeared. You can think of this program as an example of a pattern called "traverse and count." The elements of this pattern are:

  • A set or container that can be traversed, like an array or a string.
  • A test that you can apply to each element in the container.
  • A counter that keeps track of how many elements pass the test.

In this case, I have a method in mind called inBucket that counts the number of elements in an array that fall in a given bucket. The parameters are the array and two doubles that specify the lower and upper bounds of the bucket.

  public static int inBucket (double[] a, double low, double high) {
    int count = 0;
    for (int i=0; i<a.length; i++) {
      if (a[i] >= low && a[i] < high) count++;
    return count;

I haven't been very careful about whether something equal to low or high falls in the bucket, but you can see from the code that low is in and high is out. That should prevent me from counting any elements twice.

Now, to divide the range into two pieces, we could write

    int low = inBucket (a, 0.0, 0.5);
    int high = inBucket (a, 0.5, 1.0);

To divide it into four pieces:

    int bucket1 = inBucket (a, 0.0, 0.25);
    int bucket2 = inBucket (a, 0.25, 0.5);
    int bucket3 = inBucket (a, 0.5, 0.75);
    int bucket4 = inBucket (a, 0.75, 1.0);

You might want to try out this program using a larger numValues. As numValues increases, are the numbers in each bucket levelling off?

Last Update: 2011-01-24