描述

给一个升序的数组，以及一个 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.

标签

二分法

相关题目

搜索区间

代码实现

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) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        int count = 0;
        if (A[start] == target) {
            for (int i = start; i < A.length; i++) {
                if (A[i] == target) {
                    count++;
                }
            }
            return count;
        }
        if (A[end] == target) {
            for (int i = end; i < A.length; i++) {
                if (A[i] == target) {
                    count++;
                }
            }
            return count;
        }
        return 0;
    }
}