Java Solution - O(log n)


#1
public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int findCount(final int[] a, int target) {
        if(a.length < 1)
            return 0;
        int l = binarySearch(a, target, true);
        if(l == -1)
            return 0;
        int r = binarySearch(a, target, false);
        return r-l+1;
    }
    public int binarySearch(int[] a, int target, boolean searchFirst) {
        int start = 0, end = a.length-1, result = -1;
		while(start <= end) {
			int mid = (start+end)/2;
			if(target == a[mid]) {
			    result = mid;
			    if(searchFirst) 
			       end = mid-1;
			    else
			       start = mid+1;
			}
			else if(target < a[mid])
				end = mid-1;
			else
				start = mid+1;
		}
		return result;
    }
}