Suppose company X has hired you as a software engineer. Company X is desperate t
ID: 3665637 • Letter: S
Question
Suppose company X has hired you as a software engineer. Company X is desperate to improve the run time of their software. Rather than allow you to use the standard binary search algorithm, company X demands you create a new version. Since recursively dividing the array into two parts is so efficient for searching, the bigwigs at company X conclude dividing the array into three parts will be even more efficient. This new "3-ary" search divides the given sorted array into 3 equal sized sorted subarrays. It finds which subarray will contain the given value and then recursively searches that subarray. If the given value is in the array you should return true. Otherwise you should return false. Write up this new recursive algorithm using pseudocode. Create a recurrence to represent the worst case run time of our new ";3-ary" search from the pseudocode. Use master theorem to solve you above recurrence relation. Compare this asymptotic run time to that of binary search. Does our new algorithm perform significantly better than binary searchExplanation / Answer
1 Q Answer:
Pseudo Code:
Define procedure as int Array search it contains that passes three array types as integer and imin, imax ,key as integer type {
If imax is less than imin then
return as key_not_found
else
imod = midpoint(imin, imax)
if(A[mid] >key)
return Arraysearch(A,key,imin, imid-1)
else if(A[mid]<key)
return Arraysearch(A,key.imid+1,imax);
else
return imid
}