面试题38：数字在排序数组中出现的次数

考察二分查找，找到第一个k和最后一个k，注意二分查找while (start <= end)是 <=以及如果找不到返回-1，然后再做处理

 1 int GetFirstK(int* data, int length, int k, int start, int end)
 2 {
 3     while (start <= end)
 4     {
 5         int mid = (start + end) / 2;
 6         if (data[mid] == k)
 7         {
 8             if (mid == 0 || data[mid - 1] != k)
 9                 return mid;
10             else
11                 end = mid - 1;
12         }
13         else if (data[mid] > k)
14             end = mid - 1;
15         else if(data[mid] < k)
16             start = mid + 1;
17     }
18     return -1;
19 }
20 
21 int GetLastK(int* data, int length, int k, int start, int end)
22 {
23     while (start <= end)
24     {
25         int mid = (start + end) / 2;
26         if (data[mid] == k)
27         {
28             if (mid == length - 1 || data[mid + 1] != k)
29                 return mid;
30             else
31                 start = mid + 1;
32         }
33         else if (data[mid] > k)
34             end = mid - 1;
35         else if (data[mid] < k)
36             start = mid + 1;
37     }
38     return -1;
39 }
40 
41 
42 int GetNumberOfK(int* data, int length, int k)
43 {
44     int first = GetFirstK(data, length, k, 0, length - 1);
45     int last = GetLastK(data, length, k, 0, length - 1);
46     if(data == NULL || first == -1 || last == -1)
47         return 0;
48     else
49         return last - first + 1;
50 
51 }