剑指offer——数字在排序数组中出现的次数

通过二分查找，找到k在数组中第一次出现的位置和最后一次出现的位置。

#include <iostream>
using namespace std;

int GetFirstK(int *data,int length,int k,int start,int end)
{
 if (start>end)
 {
  return -1;
 }
 int middleIndex=start+(end-start)/2;
 int middleData=data[middleIndex];
 if (middleData==k)
 {
  if (middleIndex>0&&data[middleIndex-1]!=k||middleIndex==0)
  {
   return middleIndex;
  }
  else
  {
   end=middleIndex-1;
  }
 }
 else if(middleData>k)
 {
  end=middleIndex-1;
 }
 else
 {
  start=middleIndex+1;
 }
 return GetFirstK(data,length,k,start,end);
}

int GetLastK(int *data,int length,int k,int start,int end)
{
 if (start>end)
 {
  return -1;
 }
 int middleIndex=start+(end-start)/2;
 int middleData=data[middleIndex];
 if (middleData==k)
 {
  if (middleIndex<length-1&&data[middleIndex+1]!=k||middleIndex==0)
  {
   return middleIndex;
  }
  else
  {
   start=middleIndex+1;
  }
 }
 else if(middleData>k)
 {
  end=middleIndex-1;
 }
 else
 {
  start=middleIndex+1;
 }
 return GetLastK(data,length,k,start,end);
}

int GetNumberOfK(int* data,int length,int k)
{
 int number=0;
 if (data!=NULL&&length>0)
 {
  int first=GetFirstK(data,length,k,0,length-1);
  int last=GetLastK(data,length,k,0,length-1);
  if (first>-1&&last>-1)
  {
   number=last-first+1;
  } 
 }
 return number;
}

int main()
{
 int a[]={1,2,2,2,3,3,3,3,3,3,4,4,5,6};
 cout<<GetNumberOfK(a,14,3)<<endl;
 return 0;
}