描述

给一个升序的数组，以及一个target，找到它在数组中出现的次数。

样例

给出 [1, 3, 3, 4, 5] target = 3, 返回 2.
给出 [2, 2, 3, 4, 6] target = 4, 返回 1.
给出 [1, 2, 3, 4, 5] target = 6, 返回 0.

挑战

Time complexity in O(logn)

代码

public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int totalOccurrence(int[] A, int target) {
        // Write your code here
        int n = A.length;
        if (n == 0) {
            return 0;
        }
        if (A[n-1] < target || A[0] > target) {
            return 0;
        }
        
        int l = 0, r = n - 1;
        int start = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (A[mid] >= target) {
                start = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        if (A[start] != target)
            return 0;

        int end = n - 1;
        l = 0; r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (A[mid] <= target) {
                end = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        return end - start + 1;
    }
}