剑指offer之面试题38数字在排序数组中出现的次数

问题描述：

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

例如：

输入排序数组{1,2,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。

实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

int findLastK(int *num,int left,int right,int len,int k){
if(left>right){
return -1;
}
int mid = (left+right)/2;
int middate =num[mid];

if(middate==k){
if((mid<len && num[mid+1]!=k) || mid == len){
return mid;
}else{
left = mid+1;
}
}else if(middate>k){
right=mid-1;
}else if(middate<k){
left=mid+1;
}
return findLastK(num,left,right,len,k);
}

int findFirstK(int *num,int left,int right,int len,int k){
if(left>right){
return -1;
}
int mid = (left+right)/2;
int middate =num[mid];

if(middate==k){
if((mid>0 && num[mid-1]!=k) || mid == 0){
return mid;
}else{
right = mid-1;
}
}else if(middate>k){
right=mid-1;
}else if(middate<k){
left=mid+1;
}
return findFirstK(num,left,right,len,k);
}


int getNumberOfK(int *num,int len,int k){
int rs = 0;
if(num!=NULL && len >0){
int last =findLastK(num,0,len-1,len,k);
int first=findFirstK(num,0,len-1,len,k);
if(last>-1 && first>-1){
rs = last -first+1;
}
}
return rs;
}

int main(int argc, char *argv[])
{
int num[]={
1,2,3,3,3,3,4
};
int k ;
scanf("%d",&k);
int len = sizeof(num)/sizeof(int);
int rs =getNumberOfK(num,len,k);
printf("%d\n",rs);
return 0;
}

参考资料：
剑指offer

备注：
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51383949
作者：WSYW126