1. 先用二叉搜索找到结点的下标
2. 如果找到就从这个下标开始往左右搜索。
3. 否则返回找不到。
import java.util.Arrays;
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int index = binSearch(array,k);
if(index<0) return 0;
int sum=1;
for(int i=index-1;i>=0;i--){
if(array[i] == k) sum++;
}
for(int i=index+1;i<array.length;i++){
if(array[i] == k) sum++;
}
return sum;
}
int binSearch(int[] a, int k){
int hi=a.length-1;
int lo=0;
while(lo <= hi){
int mid = (hi+lo) >>> 1;
if(a[mid] == k){
return mid;
}else if(a[mid] > k){
hi = mid-1;
}else {
lo = mid+1;
}
}
return -1;
}
}