Count the number of occurrences of a given key in an array

This was asked in on-site Microsoft interview (see original post).  It seems the answers to this question are not correct.  This question can be solved in O(logN) with binary search.  We know how to find the first occurrence of a given key in a sorted array (see my previous post).  It is easy to modify the algorithm to find the last occurrence of the given key in a sorted array:

    /**
     * find the last occurrence of the target in a sorted array
     * @param input a sorted array
     * @param target
     * @return the last index of target or -1
     */
    public static int findLastOccurence(int[] input, int target) {
        int lower = -1;
        int upper = input.length;

        while (lower + 1 != upper) {
            int  middle = (lower + upper) >>> 1;

            if (input[middle] > target) {
                upper = middle;
            } else {
                lower = middle;
            }
        }

        if (lower != -1 && input[lower] == target) {
            return lower;
        } else {
            return -1;
        }
    }

After knowing indexes of the first and last occurrences, it is easy to know the number of occurrences (or the range).  The run time for finding the number of occurrences is O(logN) since finding first and last occurrences is O(logN).