#include<iostream>using namespace std;int countOfNumFromSortArr(int arr[],int len,int num);int main(){ int arr[]={0,1,1,2,2,2,2,3,3,3,4}; int n; cin>>n; cout<<countOfNumFromSortArr(arr,sizeof(arr)/sizeof(int),n)<<endl; return 0; }int countOfNumFromSortArr(int arr[],int len,int num){ if(arr==NULL||len==0) return -1; int left=0; int right=len-1; int mid; while(left<=right) // 查找算法的复杂度为lg(n) { mid=(left+right)/2; if(arr[mid]==num)// 找到该数字; break; else if(arr[mid]>num) right=mid-1; else left=mid+1; } if(left>right)// 没有找到该数字 return 0;
int first;int last; //用来记录num的第一个和最后一个下标 int mid_left,mid_right; if(arr[mid-1]!=num) first=mid; else { left=0; right=mid-1; // 上面找到的Num的位置 while(right-left!=1) // 关键1 { mid_left=(left+right)/2; if(arr[mid_left]==num) right=mid_left; // 关键2 else left=mid_left; } if(arr[left]==num) first=left; else first=right; } if(arr[mid+1]!=num) last=mid; else { left=mid+1; right=len-1; while(right-left!=1) { mid_right=(left+right)/2; if(arr[mid_right]==num) left=mid_right; else right=mid_right; } if(arr[right]==num) last=right; else last=left; } return last-first+1;}
转载于:https://www.cnblogs.com/fchy822/p/4796090.html
