【js实现】在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次

      今天做笔试题的时候做到了这题，当时由于时间 太短，而且因为没有处理好JavaScript中整数的关系，导致结果没有运行出来。所以在结束之后，在网上搜了资料，发现都是用C语言或者C++，java实现的，没有用JavaScript实现的，于是我又重新做了这道题。

思路分析：

1、首先这个数组是有序的，所以我们只要能够找到这个给定的数字在这个数组中出现的第一个位置和最后一个位置就可以得到一共出现的次数；
2、在这里采用二分查找的方法可以更快速的找到第一个位置和最后一个位置，减少时间复杂度，最坏情况下的时间复杂度为为O(logn)；

具体实现方法：

function getUpper(arr, key){
//获取某个元素最后出现位置 
    var low = 0, high = arr.length - 1;
    console.log(high);
    var mid = Math.round((low + high) / 2);
    console.log(mid);
    /*其实是一个递归迭代*/ 
    while(low <= high){

        if(arr[mid] <= key){
         //当要查找的值比中位数大于等于时，把查找的低位限制为mid+1
            low = mid + 1;
        }else{
         //当要找的值比 中位数小时，把查找的高位限制为mid-1 
            high = mid - 1;  
        }
        mid = Math.round((low + high) / 2);

    } 
// 返回最后出现位置 
    return high; 
}

function getLower(arr,key){//获取某个元素第一次出现位置 
    var low = 0, high = arr.length - 1;
    var mid = Math.round((low + high) / 2);
    while(low <= high){      
        //当要找的值比 中位数小于等于时，把查找的高位限制为mid+1 
        if(arr[mid] >= key){
            high = mid -1;
        }else{
        //当要找的值比 中位数大时，，把查找的低位限制为mid+1 
            low = mid + 1;
        }
        mid = Math.round((low + high) / 2);       
    }    
    //返回第一次出现位置 
    return low; 
} 

var arr = [0,1,1,2,2,2,2,4,4,4]; //测试数组 
var key = 4;
var higher = getUpper(arr,key);
var lower = getLower(arr,key);
console.log(higher-lower+1);