初始解法

• 二分法查找上界（k值）与下界（k值），相减得到个数

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int start = 0, end = array.length - 1, result = 0, kStart = 0, kEnd = array.length - 1;
        // 找该值左端点
        while(start <= end){
            kStart = (start + end) / 2;
            if(k == array[kStart] && (kStart == 0 || kStart == array.length - 1 || array[kStart - 1] != k)) {
                break;
            } else if(k <= array[kStart]) {
                end = kStart - 1;
            } else {
                start = kStart + 1;
            }
        }
        // 未找到
        if(start > end) {
            return 0;
        }

        // 找该值右端点
        start = kStart;
        end = array.length - 1;
        while(start <= end){
            kEnd = (start + end) / 2;
            if(k == array[kEnd] && (kEnd == 0 || kEnd == array.length - 1 || array[kEnd + 1] != k)) {
                break;
            } else if(k < array[kEnd]) {
                end = kEnd - 1;
            } else {
                start = kEnd + 1;
            }
        }
        return kEnd - kStart + 1;
    }
}

优化解法

• 下界是k值（存在）或者是比k值大的值（不存在），上界是比k值大的值
• temp = (start + end - start) / 2可以保证start和end相邻时取start而不影响其他情况
• 由上，左侧增长而右侧不增长既不会死循环也就可以保证结果偏大

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int start = 0, end = array.length, result = 0, kStart = 0, kEnd = array.length;
        // 找该值左端点
        while(start < end){
            kStart = start + (end - start) / 2;
            if(k <= array[kStart]) {
                end = kStart;
            } else {
                start = kStart + 1;
            }
        }
        kStart = start;

        // 找该值右端点
        start = 0;
        end = array.length;
        while(start < end){
            kEnd = start + (end - start) / 2;
            if(k < array[kEnd]) {
                end = kEnd;
            } else {
                start = kEnd + 1;
            }
        }
        kEnd = start;
        return kEnd - kStart;
    }
}