//题目:给出排序数组,给出一个数,返回这个数的出现次数
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(findCount(new int[]{1},1));
}
public static int findCount(int[] input,int num) {
int first = findFirstIndex(input,num);
int last = findLastIndex(input, num);
if(first == -1 || last == -1){
return 0;
}else{
return last-first+1;
}
}
public static int findFirstIndex(int[] input, int num){ //找到第一次出现这个数的下标
int low = 0;
int high = input.length-1;
boolean found = false;
while(low<=high){
int mid = (low+high)/2;
if(input[mid] == num){
found = true;
}
if(input[mid]<num){
low = mid+1;
}else{
high = mid-1;
}
}
if(found == false){
return -1;
}
return high+1;
}
public static int findLastIndex(int[] input, int num){ //找到最后一次出现这个数的下标
int low = 0;
int high = input.length-1;
boolean found = false;
while(low<=high){
int mid = (low+high)/2;
if(input[mid] == num){
found = true;
}
if(input[mid]>num){
high = mid-1;
}else{
low = mid+1;
}
}
if(found == false){
return -1;
}
return low-1;
}
}