数字在数组中出现，复杂度为log n算法，复杂度为c.

Question

天才你好，祝你有美好的一天:

T [M]数组按升序排序。
写一个算法计算整数x在数组T[M]中出现的次数。
 x与T的元素比较的次数，必须是log n阶

我的尝试是:

def Occurrence(T,X,n):{
   
 
       if ( n=0 ){ return 0;}
        else { 
            Occurrence(T,X,n/2);
            if( T[n]==X ){  return 1+Occurrence(T,x,n/2); }
            else { return Occurrence(T,x,n/2); }
 
 }the end of code
complexity is :
                   0 if n=0
we have      O(n)={
                   1+O(n/2) if n>0
O(n)=1+1+1+....+O(n/2^(n))=n+O(2/2^(n))
when algorithm stopp if{existe k  n=2^(k),so   O(n)=n+1 } 
n/2^(n)=1)  =>   O(n)=log(n)+1, so you think my code is true ?
</pre>

Answer 1

查看二进制搜索变体，该变体给出所需元素的最左和最右索引，然后返回index_difference + 1

您可以在c++ STL中使用lower_bound和upper_bound，在Python中使用bisect_left和bisect_right，如果有类似的函数，或者从Wiki引文中实现伪代码。

Answer 2

如果数组已排序

import bisect 
T = [1, 3, 4, 4, 4, 6, 7]
x = 4
right = bisect.bisect(T, x)
if(right == 0 or T[right - 1] != x):
    print("Count:0")
else:
    left = bisect.bisect_left(T, x)
    print("Count:", right - left)

2 log (n)