二分查找

数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数，例如输入排序数组{0, 1, 2, 3, 4, 4, 4, 4, 5}和数字4，由于4在这个数组中出现了4次，因此输出4。（出自：剑指offer）

既然输入的数组是排序的，那么很自然地就能想到用二分查找算法。

 1 #include <iostream>
 2 
 3 int getFirstK( int *data, int length, int k, int start, int end )
 4 {
 5     if ( start > end )
 6     {
 7         return -1;
 8     }
 9     int midIndex = ( end + start ) / 2;
10     int midValue = data[ midIndex ];
11     if ( midValue == k )
12     {
13         if ( ( midIndex > 0 && data[ midIndex - 1 ] != k ) || midIndex == 0 )
14         {
15             return midIndex;
16         }
17         else
18         {
19             end = midIndex - 1;
20         }
21     }
22     else if ( midValue > k )
23     {
24         end = midIndex - 1;
25     }
26     else
27     {
28         start = midIndex + 1;
29     }
30     return getFirstK( data, length, k, start, end );
31 }
32 
33 int getLastK( int *data, int length, int k, int start, int end )
34 {
35     if ( start > end )
36     {
37         return -1;
38     }
39     int midIndex = ( end + start ) / 2;
40     int midValue = data[ midIndex ];
41     if ( midValue == k )
42     {
43         if ( ( midIndex > 0 && data[ midIndex + 1 ] != k ) || midIndex == length - 1 )
44         {
45             return midIndex;
46         }
47         else
48         {
49             start = midIndex + 1;
50         }
51     }
52     else if ( midValue > k )
53     {
54         end = midIndex - 1;
55     }
56     else
57     {
58         start = midIndex + 1;
59     }
60     return getLastK( data, length, k, start, end );
61 }
62 
63 int getNumbersOfK( int *data, int length, int k )
64 {
65     int num = 0;
66     if ( data != NULL || length > 0 )
67     {
68         int first = getFirstK( data, length, k, 0, length - 1 );
69         int last = getLastK( data, length, k, 0, length - 1 );
70         if ( first > -1 && last > -1 )
71         {
72             num = last - first + 1;
73         }
74     }
75     return num;
76 }
77 
78 int main()
79 {
80     int data[] = {0, 1, 2, 3, 4, 4, 4, 4, 5};
81     int ret4 = getNumbersOfK( data, 9, 4);
82     std::cout << "4 appear " << ret4 << " times in data." << std::endl;
83     int ret6 = getNumbersOfK( data, 9, 6 );
84     std::cout << "6 appear " << ret6 << " times in data." << std::endl;
85 
86     return 0;
87 }

View Code