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

题目：

统计一个数字在排序数组中出现的次数。例如：输入排序数组是{1,2,3,3,3,3,4,5}，由于这个3在这个数组中出现了4次，因此输出为4。

解答：

 1 public class Solution {
 2 
 3     public static void main(String[] args) {
 4         int[] arr1 = {1,2,3,3,3,3,4,5};
 5         int target1 = 4;
 6 
 7         System.out.println(getNumberOfK(arr1, target1));
 8 
 9         int arr2 = {2,2,2,2,2};
10         int target2 = 2;
11         System.out.println(getNumberOfK(arr2, target2));
12     }
13 
14     public static int getNumberOfK(int[] arr, int k) {
15         if(arr == null) {
16             return 0;
17         }
18 
19         int number = 0;
20         int first = getFirst(arr, k, start, end);
21         int lat = getLast(arr, k, start, end);
22 
23         if(first > -1 && last > -1) {
24             number = last-first+1;
25         }
26 
27         return number;
28     }
29 
30     private static int getFirst(int[] arr, int k, int start, int end) {
31         if(start > end) {
32             return -1;
33         }
34 
35         int mid = (start+end)>>1;
36         if(k == arr[mid]) {
37             if(mid > 0 && arr[mid-1] != k) {
38                 return mid;
39             } else {
40                 end = mid - 1;
41             }
42         } else if(arr[mid] > k) {
43             end = mid - 1;
44         } else {
45             start = mid + 1;
46         }
47 
48         return getFirst(arr, k, start, end);
49     }
50     
51 
52     private static int getLast(int[] arr, int k, int start, int end) {
53         if(start > end) {
54             return -1;
55         }
56 
57         int mid = (start+end)>>1;
58         if(arr[mid] == k) {
59             if(mid < arr.length-1 && arr[mid] != k) {
60                 return mid;
61             } else {
62                 start = mid + 1;
63             } else if(arr[mid] > k) {
64                 end = mid - 1;
65             } else {
66                 start = mid + 1;
67             }
68         }
69 
70         return getLast(arr, k, start, end);
71     }
72 }