It is possible to change the way that we pick the dividing point in a binary...

Transcribed Image Text:

It is possible to change the way that we pick the dividing point in a binary search, and still get a working search routine. However, where we pick the dividing point could affect the performance of the algorithm. Let us denote with low the starting index and with high the finishing index of the array. If we change the dividing point computation in function binary search from i (low + high)/2 to i = (low + ((high - low)/3)). i. First, complete the missing statements in the binary search. RECURSIVE-BINARY-SEARCH(A, v, low, high) if low > high then return NIL mid + low+(high -low)/3 if v = A[mid] then return mid else if v > A[mid] then return RECURSIVE-BINARY-SEARCH( else return RECURSIVE-BINARY-SEARCH( ii. Give the recurrence T(n) of the running time: iii. What is the time complexity? It is possible to change the way that we pick the dividing point in a binary search, and still get a working search routine. However, where we pick the dividing point could affect the performance of the algorithm. Let us denote with low the starting index and with high the finishing index of the array. If we change the dividing point computation in function binary search from i (low + high)/2 to i = (low + ((high - low)/3)). i. First, complete the missing statements in the binary search. RECURSIVE-BINARY-SEARCH(A, v, low, high) if low > high then return NIL mid + low+(high -low)/3 if v = A[mid] then return mid else if v > A[mid] then return RECURSIVE-BINARY-SEARCH( else return RECURSIVE-BINARY-SEARCH( ii. Give the recurrence T(n) of the running time: iii. What is the time complexity?