剑指OfferJZ37：数字在升序数组中出现的次数-java版

JZ37:统计一个数字在升序数组中出现的次数

统计一个数字在升序数组中出现的次数，那么这个数在数组中的排序一定是连续的 二分查找定义：它是一种效率较高的查找方法。但是，二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

在排序好的数组中查找数字，可以使用二分法来查找

二分查找过程：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

另外声明一下，计算 mid 时需要技巧防止溢出，我们不写mid=（left+right）/2，建议写成: mid = left + (right - left) / 2，偶数的时候：取n/2取整，实际上剩下的序列是 索引为取整左边的序列。

那么查找一个数字在升序数组中出现的次数步骤： 二分查找这个数（k）在数组中的起始位置和在数组中的结束位置，然后拿 结束位置-开始位置+1 就是这个数在数组中出现的次数 二分查找定义左节点l和右节点r（l>1 代表 r-l的值右移1位，相当于r-l的值除以2取整，这样写计算效率高 if(array[mid]==k){//k等于中间值 if(mid-1>=0 && array[mid-1]==k){ //说明mid当前的位置不是初始位置，k的初始位置在1~mid-1区间 r=mid-1;//缩小区间 }else { //就可以说明mid位置的数字就是k的初始位置 return mid; } }else if(array[mid]>k){//k小于中间值 r=mid-1;//k的初始位置在1~mid-1区间 }else {//k大于中间值 l=mid+1;//k的初始位置在mid+1~r区间 } } return l; } //找到一个数在数组中的终止位置 private int findLastPosition(int[] array,int k){ int l=0; int r=array.length-1; while(l>1);//(r - l)>>1 代表 r-l的值右移1位，相当于r-l的值除以2取整，这样写计算效率高 if(array[mid]==k){//k等于中间值 if(mid+1k){//k小于中间值 r=mid-1;//k的初始位置在1~mid-1区间 }else {//k大于中间值 l=mid+1;//k的初始位置在mid+1~r区间 } } return l; } public int GetNumberOfK(int [] array , int k) { if(array.length==0){ return 0; } int firstPosition = findFirstPosition(array, k); int lastPosition = findLastPosition(array, k); if(array[firstPosition]!=k){ return 0; } return lastPosition-firstPosition+1; }