Read the following pseudocode, note that A is a sorted array: BINARY-SEARCH(A, v) low := 1 high := n while low A[mid] low = mid

Read the following pseudocode, note that A is a sorted array: BINARY-SEARCH(A, v)

low := 1

high := n

while low <= high

mid = floor((low+ high)/2)

if v == A[mid]

return mid

else if v > A[mid]

low = mid + 1

else

high = mid - 1

return NIL

a) Find the Recurrence Relation.

b) Is there a tight bound? If the answer is yes, find it.

c) Find the best case and worst case running time.