Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn)
Examples:

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 2
Output: 4 // x (or 2) occurs 4 times in arr[]

对有序数组，找到元素 x 的左右边界即可。
注意二分的时候，左右的访问顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
  #include <bits/stdc++.h>
using namespace std;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define pfc(c) printf(c)
#define fi(i,s,t) for(int i=s;i<t;i++)
const int MAX=10000+10;
int n,a[MAX],x; 
int first(int a[], int l, int r, int x) {
	if(r<l) return -1;
	int m= (l+r)/2;
	if(( m == 0 || x > a[m-1]) && a[m] == x) 
      	return m; 
	else if(x>a[m])  //先右边
		return first(a,m+1,r,x);
	else 
		return first(a,l,m-1,x);
}
int last(int a[], int l, int r, int x) {
	if(r<l) return -1;
	int m= (l+r)/2;
	if(( m == n-1 || x < a[m+1]) && a[m] == x) 
      	return m; 
	else if(x<a[m]) 
		return last(a,l,m-1,x);
	else 
		return last(a,m+1,r,x);
}
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,0,n)
		sf(a[i]);
	sf(x);
	pf(last(a,0,n,x) - first(a,0,n,x) +1);
	return 0;
}