The following algorithm has access to a global list of distinct integers a1,a2,..., an. When called with parameters i,j, r, Search(i,j,x) returns the location of the target value r among [a,aj), or 0 if the target value is not present in [a,.,ajj. procedure Search(i,j, z : i,j,z ntegers, 1- iS j n) I. ifai = 1 then 2. return i 3. else if i=j then 1 5. else 6.return Search(i +1,j, z) return (0 Let T(n) be the running time of this algorithm. Write a recurrence relation that T(n) satisfies. Then solve the recurrence and write the solution in notation