// pre : elements low through high of list are in sorted (nondecreasing)
    //       order
    // post: returns the index of the given key in the list, 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, 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.
    }