1.題目：
有序數(shù)組中目標(biāo)元素出現(xiàn)的次數(shù)铃诬，要求時(shí)間復(fù)雜度為O(logn)。
2.思想
數(shù)組前提是有序的，因此主要用到了二分查找的思想礁鲁，找到目標(biāo)值后盐欺，繼續(xù)向左或者向右查找第一次出現(xiàn)的位置或者最后一次出現(xiàn)的位置，直到?jīng)]有再找到目標(biāo)值仅醇，那么最后一次記錄的索引值就是我們要找的位置冗美。那為什么不在找到目標(biāo)值后從中間開始往左右兩邊遍歷計(jì)數(shù)，這樣也可以確定目標(biāo)值的個(gè)數(shù)呀析二。但是如果目標(biāo)值的個(gè)數(shù)很多墩衙，這樣豈不是就轉(zhuǎn)換成順序查找了嗎，復(fù)雜度為O(n)甲抖，因此失去了二分查找的意義漆改。
3.代碼
public class 有序數(shù)組中某元素的個(gè)數(shù)logN {
public static void main(String[] args) {
int[]arr={1,1,3,4,5,5,5,6,7};
int target=3;
int left=find(arr,target,0);
int right=find(arr,target,1);
if(left==-1){
System.out.println(0);
}else{
System.out.println(right-left+1);
}
}
public static int find(int[]arr,int target,int flag){
if(arr.length==0)return -1;
int left=0;
int right=arr.length-1;
int last=-1;
while(left<=right){
int mid=(left+right)/2;
if(arr[mid]>target){
right=mid-1;
}else if(arr[mid]<target){
left=mid+1;
}else {
last=mid;
if(flag==0){//找第一個(gè)值等于target的索引
right=mid-1;//在左邊繼續(xù)查找
}else if(flag==1){//找最后一個(gè)值等于target的索引
left=mid+1;//在右邊繼續(xù)查找
}
}
}
return last;
}
}
