Write C++ code, algorithm and time complexity

Design a recursive algorithm to perform binary search Binary-Search(A,key,lb,ub) on a list of numbers A in non-decreasing order, where key is the element to be searched in A, Ib and ub are lower and upper bounds of A, and number of elements in A, n=ub-lb+1. Consider the following conditions O Searching key in empty A. key not matched in non-empty A. key is matched in A, and report its position. Construct the recurrence relation for the algorithm. Solve it to find the time complexity. Compare time-space required by recursive and iterative versions of binary search