Total Occurrence of Target

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

Example Given [1, 3, 3, 4, 5] and target = 3, return 2.

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

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

Notes:

• Basic Binary search: two passes
• Find the most left one which equals with target
• Find the most right one which equals with target
• Get the number

     public int totalOccurrence(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }

        if (A[0] > target || A[A.length-1] < target) {
            return 0;
        }

        // left - find the last one which is smaller than target
        int left = -1;
        int start = 0;
        int end = A.length-1;
        while(start+1 < end) {
            int middle = start + (end-start)/2;
            if (A[middle] >= target) {
                end = middle;
            } else {
                start = middle;
            }
        }

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

        if (left == -1) {
            return 0;
        }

        // right - find the frist one which is bigger than target
        int right = -1;
        start = 0;
        end = A.length-1;
        while(start+1 < end) {
            int middle = start + (end-start)/2;
            if (A[middle] <= target) {
                start = middle;
            } else {
                end = middle;
            }
        }

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

        // result, right-left
        return right-left+1;
    }