1. 题目描述

统计一个数字在排序数组中出现的次数。

2. 题目分析

1. 题主一开始的方法：看见有序，使用二分，查找到target，向前向后分别遍历到不等于target的数字，因为数组中的target出现的次数是不确定的，所以，可能查找到n次，相当于O(n);
2. 面试中，这种写***被paas掉，所以我们需要用二分查找找到第一次出现target的下标，最后一次出现target的下标，
3. 对于target出现的第一次下标,采用以下方式
   当mid == 0的时候，也就是证明当前的数是从下标0开始的，则直接返回0(mid)
   为了防止数组的越界，我们需要使当前的mid>0且array[mid-1]!=key
   对于：right = mid - 1;我们可以理解成当前的key是位于中间的那一个，所以我们需要减少范围，也就是缩小right的值，让mid向前遍历。

        if (array[mid] == key) {
                if ((mid == 0) || (mid > 0 && array[mid - 1] != key)) {
                    return mid;
                } else {
                    right = mid - 1;
                }
        }

4. 对于target出现的最后一次下标，采取以下方式
   当mid == array.lenth - 1的时候，也就是证明当前的数一直到最后。则直接返回mid
   为了防止数组的越界，我们需要使当前的mid<array.lenth - 1且array[mid+1]!=key
   对于：i = mid + 1;我们可以理解成当前的key是位于中间的那一个，所以我们需要减少范围，也就是扩大left的值，让mid向后遍历。

        if (array[mid] == key) {
                if (mid == array.length - 1 || mid < array.length - 1 && array[mid + 1] != key)   {
                    return mid;
                } else {
                    left = mid + 1;
                }
        }

5. 最后，我们返回（第二次出现的下标 - 第一次出现的下标 + 1）

3. 题目代码

class Solution {
    public int search(int[] nums, int target) {
        int num1 = erfenFirst(nums, 0, nums.length - 1, target);
        int num2 = erfenSecond(nums, 0, nums.length - 1, target);
        return num2 - num1 + 1;
    }

    public static int erfenFirst(int[] array, int left, int right, int key) {
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (array[mid] == key) {
                if ((mid == 0) || (mid > 0 && array[mid - 1] != key)) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else if (array[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return 1;
    }

    public static int erfenSecond(int[] array, int left, int right, int key) {
        int i = left;
        int j = right;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (array[mid] == key) {
                if (mid == array.length - 1 || mid < array.length - 1 && array[mid + 1] != key) {
                    System.out.println(mid);
                    return mid;
                } else {
                    i = mid + 1;
                }
            } else if (array[mid] > key) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return 0;
    }
}