For the following Binary search algorithm, write its recurrence equation and solve it by giving an asymptotic upper bound.

BINARYSEARCH(A, l, r, key) //Array, left, right and the search key

1 if l <= r

2 m = (l + r) /2

3 if A[m] == key

4 return m

5 else if A[m] < key

6 return BINARYSEARCH(A, m+1, r, key)

7 else

8 return BINARYSEARCH(A, l, m-1, key)