Given a target number and an integer array sorted in ascending order. Find the total number of occurrences of target in the array.

Have you met this question in a real interview?

Yes

Example

Given[1, 3, 3, 4, 5]and target =3, return2.

Given[2, 2, 3, 4, 6]and target =4, return1.

Given[1, 2, 3, 4, 5]and target =6, return0.

it is similar to the search for a range where you have to get the left boundary and the right boudary, and substract for the final count(last - first + 1)

there is a optimization can be done, once find the left boundary, we can use the left boundary as the start to search for the right.

this problem if you don't optimize it will run over limit time for a large problem

public class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] A, int target) {
        // write your code here
        int[] ans = new int[2];
        ans[0] = -1;
        ans[1] = -1;
        if (A == null || A.length == 0) {
            return ans;
        }


        //find first
        ans[0] = findFirst(A, target);
        if (ans[0] == -1) {
            return ans;
        }

        ans[1] = findLast(A, target);
        return ans;
    }

    public int findFirst(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] > target) {
                end = mid;
            } else if (A[mid] == target) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (A[start] == target) {
            return start;
        } else if (A[end] == target) {
            return end;
        }

        return -1;
    }

    public int findLast(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] > target) {
                end = mid;
            } else if (A[mid] == target) {
                start = mid;
            } else {
                start = mid;
            }
        }

        if (A[end] == target) {
            return end;
        } else if (A[start] == target) {
            return start;
        }

        return -1;
    }
}