Simple elegant and easy to think


#1

class Solution:
# @param A : tuple of integers
# @param B : integer
# @return an integer

def bs(self,a,b,l,r):
    c=0
    if l<=r:
        m=(l+r)//2
        if b<a[m]:
            c+=self.bs(a,b,l,m-1)
        elif b>a[m]:
            c+=self.bs(a,b,m+1,r)
        elif b==a[m]:
            c+=1
            c+=self.bs(a,b,l,m-1)
            c+=self.bs(a,b,m+1,r)
    return c

def findCount(self, A, B):
    return self.bs(A,B,0,len(A)-1)