Given the binary (i.e. 2-ary) search algorithm as in the following, write the 4-ary search function....

 

Transcribed Image Text:

Given the binary (i.e. 2-ary) search algorithm as in the following, write the 4-ary search function. Empirically show that 4-ary search is faster with a sufficiently high input array size. def bsearch (A, 1, r, key): # i.e. bsearch (A, 0, len (A) -1, key) if 1 <= r: N 2 = (1+r) //2 if A[N_2] ==key: return N_2 elif A[N_2] > key: return bsearch (A, 1, N_2-1, key) return bsearch (A, N_2+1, r, key) else: else: return -1 Given the binary (i.e. 2-ary) search algorithm as in the following, write the 4-ary search function. Empirically show that 4-ary search is faster with a sufficiently high input array size. def bsearch (A, 1, r, key): # i.e. bsearch (A, 0, len (A) -1, key) if 1 <= r: N 2 = (1+r) //2 if A[N_2] ==key: return N_2 elif A[N_2] > key: return bsearch (A, 1, N_2-1, key) return bsearch (A, N_2+1, r, key) else: else: return -1

Answer rating: 100% (QA)

Below is the 4ary search function along with an empirical comparison between the 2ary search and 4ar... View the full answer