小景哥哥

37.数字在排序数组中出现的次数

发布时间：2018-08-23 00:00:00编辑：Jason浏览（246）评论（0）

37.数字在排序数组中出现的次数

题目描述

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

//暴力解决

public class Solution {
    public int GetNumberOfK1(int [] array , int k) {
       int count = 0;
        for(int i = 0; i < array.length; i++){
            if(array[i] == k)
                count++;
        }
        return count;
    }

//基于二分查找思想
    public int GetNumberOfK(int [] array , int k) {
       int count = 0;
        int index = biSearch(array, k, 0, array.length - 1);
        if(index == -1)
            return 0;
        for(int i = index; i < array.length; i++){
            if(array[i] == k)
                count++;
        }
        return count;
    }
    
    public static int biSearch(int[] array, int k, int low, int high){
        if(low > high)
            return -1;
        int mid = (low + high) / 2;
        int midData = array[mid];
        if(midData == k){
            if(mid > 0 && array[mid - 1] != k || mid == 0)
                return mid;
            else{
                while(mid > 0 && array[mid - 1] == k)
                    mid--;
                return mid;
            }
        }else if(midData > k)
            high = mid - 1;
        else
            low = mid + 1;
        return biSearch(array, k, low, high);
    }
}