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).

Find the first occurrence of an integer in sorted array

Normal binary search will return the target randomly if multiple targets are in the given array.  Below is the modified version of binary search, and it is faster than normal binary search since it requires only one comparison with each loop:

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

        while (lower + 1 != upper) {
            //avoid overflow.  See here
            int  middle = (lower + upper) >>> 1;

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

        if (upper < input.length && input[upper] == target) {
            return upper;
        } else {
            return -1;
        }
    }

The run time of above method is still O(logn).