37.数组在排序数组中出现的次数(java)

题目描述

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

解题思路

用二分法查找数字，再查找他前面和后面的，得出次数。复杂度O(logn)

public class Solution {
    public static int GetNumberOfK(int [] array , int k) {
        int high = array.length-1;
        int low = 0;
        int temp = -1;
        int count = 0;
        int mid = 0;
        while(low<=high)
        {
            mid = low +(high - low)/2;
            if(array[mid]>k)
                high = mid - 1;
            else if(array[mid]<k)
                low = mid + 1;
            else
                break;
        }
        if(low <= high){
            for(int i = mid;i >= 0;i--){
                if(array[i] == k)
                    count++;
                else
                    break;
            }
            for(int i = mid + 1;i < array.length;i++){
                if(array[i] == k)
                    count++;
                else
                    break;
            }
        }
        return count;
    }
}