剑指Offer--数字在排序数组中出现的次数

题目描述:

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

思路：

二分查找到一个等于K的位置，然后双指针，一个向前，一个向后。最后相加。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int index = bsearch(array,k);
        if(index==-1)
            return 0;
        int before = index-1;
        int next = index+1;
        int count = 0;
        while(before>=0 && array[before] ==k  ){
            count++;
            before--;
        }
        while(next<array.length && array[next] ==k  ){
            count++;
            next++;
        }
        return count+1;
    }
    
        // 输入的数组是有序的。
    public  int bsearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (target == arr[mid]) {
                return mid;
            } else if (target > arr[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }
}