// pre : elements low through high inclusive of list are in sorted
    //       (nondecreasing) order
    // post: returns the index of the given key in the list within the range
    //       low through high inclusive, returns (-(insertion point) - 1)
    //       otherwise.  The insertion point is defined as a point at which the
    //       key should be inserted to preserve sorted order.  If the list
    //       contains multiple copies of the key in the given range, there is
    //       no guarantee as to which index is returned.
    private static int binarySearch(int[] list, int key,
                                    int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            int midVal = list[mid];

            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid; // key found
            }
        }
        return -(low + 1);  // key not found.
    }