java-有序数组中指定数字出现的次数

1：时间复杂度为o(N)的情况

 private static int countNumber(int[] array, int number) {
        if (array == null || array.length <= 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == number) {
                count++;
            }
        }
        return count;
    }

这个不符合有序数组的要求，有序数组一般优先考虑到二分查找

2：时间复杂度o(logN)

总体的思路是：找到第一个出现的位置，然后从该位置起分别向左和向右查找
2.1:二分查找

 private static int binarySearch(int[] array, int start, int end, int number) {
        if (array == null || array.length <= 0 || (start == end && array[start] != number)) {
            return 0;
        }
        int middle = (start + end) / 2;
        if (array[middle] > number) {
            binarySearch(array, start, middle -1, number);
        } else if (array[middle] < number) {
            binarySearch(array,  middle + 1, end, number);
        } else {
           return middle;
        }
        return -1;
    }

首先通过二分查找找到第一个出现的位置

2.2:分别从当前位置向前和向后查找

  private static int findNumberCount(int[] array, int number) {
        if (array== null || array.length <= 0) {
            return 0;
        }
        int pos = binarySearch(array, 0, array.length -1, number);
        if (pos == -1) {
            return 0;
        }
        /* 从第一次的位置分别向前和向后查找*/
        int count = 0;
        for (int i = pos; i > 0 && array[i] == number; i--) {------>向前(左)查找
            count++;
        }
        for (int i = pos + 1; i < array.length && array[i] == number; i++) {---->向后(右)查找
            count++;
        }
        return count;
    }