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, return2.

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

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

可以用hashmap做，但是宁愿做两次二分法，也强过做while搜索，因为做while搜索最坏情况下复杂度可以达到O(n)

这道题与search for a range相似，都是用两次binary search去找左右边界。如果边界找不出来时候返回0。注意最后right-left要加1

class Solution:
    # @param {int[]} A an integer array sorted in ascending order
    # @param {int} target an integer
    # @return {int} an integer
    def totalOccurrence(self, A, target):
        # Write your code here
        if not A:
            return 0
        start, end = 0, len(A)-1
        left = 0
        while start+1 < end:
            mid = (start+end)/2
            # 左边界
            if target > A[mid]:
                start=mid
            else:
                end = mid
        if target == A[start]:
            left = start
        elif target == A[end]:
            left = end
        else:
            return 0

        start,end = 0,len(A)-1
        right = 0
        while start+1 < end:
            mid = (start+end)/2
            # 右边界
            if target >= A[mid]:
                start=mid
            else:
                end = mid
        if target == A[end]:
            right = end
        elif target == A[start]:
            right = start
        else:
            return 0

        return right - left + 1