1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int GetFistK(int* data,int length,int k,int start,int end)
{
if(start > end)
return -1;
int middleIndex = (start + end) / 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 GetFistK(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) / 2;
int middleData = data[middleIndex];
if(middleData == k)
{
if((middleIndex < length – 1 && data[middleIndex + 1] != k)||middleIndex == length -1 )
return middleIndex;
else
start = middleIndex + 1;
}
else if(middleData < k)
start = middleIndex + 1;
else
end = middleIndex – 1;
return GetLastK(data,length,k,start,end);
}
int GetNumberK(int* data,int length,int k)
{
int number = 0;
if(data != NULL && length > 0)
{
int first = GetFistK(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 data[8] = {3,3,3,3,3,3,4,5};
int k = 4;
int total=GetNumberK(data,8,k);
cout<<total<<endl;
return 0;
}
|