在一个非降序排列的数组中，找出数字target出现的次数问题解答

题目描述：

在一个非降序排列的数组中，找出数字target出现的次数。
非降序数组，比如{1，1，1，2，3，4，5，5，6}

思路一：

先通过二分查找，找到arr[index]等于target的index，在分别向前后遍历，直到arr[index] != target为止。
算法实现简单，但是当数组形如{x,x,...,x}，此时查找x的时间复杂度就退化为线性的O(n).

思路二：

1. 首先通过二分查找，找到arr[mid] == target的mid；
2. 然后分别对arr[0~mid]和arr[mid~(arr.length-1)]用二分查找，找到最左边的target的index：left，找到最右边的target的index：right；
3. return right-left+1;

Java代码实现如下：

/**
 * @author Mengjun Li
 * @create 2017/9/29
 * @since 1.0.0
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 4, 6, 7, 8, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14};
        int target = 9;
        System.out.println("输入数组中 "+target+" 的个数为 "+findNum(arr,target));
    }

    public static int findNum(int[] arr, int target) {
        if (arr == null)
            return 0;
        int len = arr.length;
        if (len < 1)
            return 0;
        if (arr[0] > target || target > arr[len - 1])
            return 0;

        int mid = findIndex(arr, 0, len - 1, target);
        if (mid == -1)
            return 0;

        int left = findLeft(arr, 0, mid, target);
        System.out.println("left=" + left);

        int right = findRight(arr, mid, len - 1, target);
        System.out.println("right= " + right);

        return right - left + 1;
    }

    private static int findLeft(int[] arr, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] == target)
                right = mid;
            else
                left = mid + 1;
        }
        return right;
    }

    private static int findRight(int[] arr, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (arr[mid] == target)
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }

    private static int findIndex(int[] arr, int left, int right, int target) {
        int mid;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (arr[mid] == target)
                return mid;
            else if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
}

输出如下：

left=6
right= 11
输入数组中 9 的个数为 6