Java solution with binary search


#1
public class Solution {
    static int findMaxIdx(List<Integer> A, int B, int L, int R) {
        if (L > R) return -1;

        int mid = (L + R) / 2;
        if (A.get(mid) < B || mid < A.size() - 1 && A.get(mid + 1) == B) {
            return findMaxIdx(A, B, mid + 1, R);
        } else if (A.get(mid) > B) {
            return findMaxIdx(A, B, L, mid - 1);
        } else if (A.get(mid) == B) {
            return mid;
        }
        return -1;
    }
    static int findMinIdx(List<Integer> A, int B, int L, int R) {
        if (L > R) return -1;

        int mid = (L + R) / 2;
        if (A.get(mid) < B) {
            return findMinIdx(A, B, mid + 1, R);
        } else if (A.get(mid) > B || mid > 0 && A.get(mid - 1) == B) {
            return findMinIdx(A, B, L, mid - 1);
        } else if (A.get(mid) == B) {
            return mid;
        }
        return -1;
    }
    public static int findCount(List<Integer> A, int B) {
        int L = 0;
        int R = A.size() - 1;
        int minIdx = findMinIdx(A, B, L, R);
        if (minIdx == -1) {
            // not found
            return 0;
        }
        int maxIdx = findMaxIdx(A, B, L, R);
        // System.out.printf("minIdx = %s, maxIdx = %s\n", minIdx, maxIdx);
        return maxIdx - minIdx + 1;
    }
}