Suppose company X has hired you as a software engineer. Company X is desperate t

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 search

Explanation / Answer

1 : Recursive psudocode for 3-ary binary search
-----------------------------------------------------------

Algorithm_for 3-ary binary search
input : Array of sortedd numbers, A[1....n],startIndex,endIndex,searchValue.

output : true - if that array contains searchValue.
false - if that array not contains searchValue.

(note that array index starts in 1 and ends in n,so initially startIndex and endIndex would be 1 and n respectivly)

================================================================================
boolean binarySearch(A,startIndex,endIndex,searchValue)
   firstMid <- startIndex+(endIndex-1)/3 { since the endIndex is the n we need total number of elements}
   secondMid <- firstMid+(endIndex-1)/3

   if A[firstMid] is equals searchValue then
       return true
   if A[secondMid] is equals searchValue then
   return true
   if A[firstMid]>searchValue then
       binarySearch(A,1,firstMid-1,searchValue)
   if A[secondMid]<searchValue then
       binarySearch(A,secondMid+1,endIndex,searchValue)

   
return binarySearch(A,firstMid+1,secondMid-1,searchValue)

====================================================================================

###########################################################################################

2 : Recurrence for worst case running time
Since the array is divided into 3 sub arrays and for comparision lets assume some constant time c then,
T(n) = T(n/3)+c = theta(log n/log3) {This is way of representing the base of that logrithm which is 3}

############################################################################################

3: Master therom {I am asssuming that you aware of Mater theorem}

T(n) = aT(n/b)+fn ====>{ in master theorm a >=1 and b>1, i.e the 'a' number of array with size of 'b' number of elements.}

if we apply the master theorm for then we get,
T(n) = T(n/3)+c ==>a = 1,b=3 ,fn=c {let c be 1}.

from the second case of Master theorem with f(n) = (nlogb a), then T(n) = (nlogb a logb n).

so we get T(n) = theta(logn/log3)

################################################################################

4 : Does this better than binary search ?

No, because log n/log3 > log n/log2

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.