Ternary search. consider the following ternary search algorithm which requires us to search for an element k in a sorted array a of size n starting at index p and ending at index q. unlike binary search, ternary search divides the array into 3 equally sized parts instead of two halves.
1: procedure TERNARYSEARCH (A,p,q,k)
2: if p≤q then
3: m₁ = p+⌊(q−p)/3⌋
4. m₂ = m₁ +⌊(q−p)/3⌋
5: if A[m₁]==k then
6: return m₁
7: end if
8: if A[m₂]==k then
9: return m₂
​10: end if
11: if k12: return TernarySearch (A,p,m₁ −1,k)
13: else if k>A[m₁] then
14: return TernarySearch (A,m₂ +1,q,k)
15: else
16: return TernarySearch (A,m₁ +1,m₂ −1,k)
17: end if
18: end if
19: end procedure
​(a) Write down the recurrence for this algorithm.
(b) Solve the recurrence using any method you prefer.