Question

Write an algorithm in pseudocode for the binary search method using a while loop (iterative version)
The recursive ternarySearch method returns true or false depending if the element was found or not.

The ternarySearch method works in a similar manner to a binary search except it uses two mid values that “divide” the array into three portions. So, it needs to consider three recursive scenarios:

See sample run:

Accounts are:

[0] 5658845

[1] 8080152

[2] 1005231

[3] 4520125

[4] 4562555

[5] 6545231

[6] 7895122

[7] 5552012

[8] 3852085

[9] 8777541

[10] 5050552

[11] 7576651

[12] 8451277

[13] 7825877

[14] 7881200

[15] 1302850

[16] 1250255

[17] 4581002

Sorted accounts are:

[0] 1005231

[1] 1250255

[2] 1302850

[3] 3852085

[4] 4520125

[5] 4562555

[6] 4581002

[7] 5050552

[8] 5552012

[9] 5658845

[10] 6545231

[11] 7576651

[12] 7825877

[13] 7881200

[14] 7895122

[15] 8080152

[16] 8451277

[17] 8777541

ternarySearch: element 7881200 is found true

   PASS

ternarySearch: element 7881199 is found false

   PASS

ternarySearch: element 7881201 is found false

   PASS

ternarySearch: element 2222222 is found false

   PASS

ternarySearch: element 9999999 is found false

   PASS

ternarySearch: element 0000000 is found false

   PASS

ternarySearch: element 1111111 is found false

   PASS

ternarySearch: element 1005231 is found true

   PASS

ternarySearch: element 8777541 is found true

   PASS

*** Done ***

Process finished with exit code 0

desired item is smaller than the element at index mid1
desired item is greater than the element at index mid2
desired item is smaller than the element at index mid2 but is greater than the element at index mid1
Utilize compareTo method, save the returned value(s) and use them in comparisons.

Use the following formulas to calculate mid indexes:

int mid1 = left + (right - left)/3;

int mid2 = right – (right - left)/3

Answer 1

The ternary search algorithm works exactly same as that of binary search with the only difference being instead of splitting the array into two parts it is split into three parts. The remaining functioning of the algorithm is same as that of binary search. The working program for ternary search is follows.

Program:

#include <iostream>
#include <algorithm>
using namespace std;

bool ternarySearch(int l, int r, int key, int a[])
{
if(r>=l)
{
int mid1=l+(r-l)/3;
int mid2=r-(r-l)/3;
if(a[mid1]==key)
{
return true;
}
if(a[mid2]==key)
{
return true;
}
if(key<a[mid1])
{
return ternarySearch(l,mid1-1,key,a);
}
else if(key>a[mid2])
{
return ternarySearch(mid2+1,r,key,a);
}
else
{
return ternarySearch(mid1+1,mid2-1,key,a);
}
}
return false;
}

int main()
{
int elements,i,l,r,key;
bool p=false;
char response='Y';
cout<<"Enter number of accounts: ";
cin>>elements;
int a[elements];
l=0;
r=elements-1;
cout<<"Accounts are:\n";
for(i=0;i<elements;i++)
{
cout<<"["<<i<<"] ";
cin>>a[i];
}
sort(a,a+elements);
cout<<"\nSorted Accounts are: ";
for(i=0;i<elements;i++)
{
cout<<"\n["<<i<<"] "<<a[i];
}

while(response=='Y'||response=='y')
{
cout<<"\nEnter element to search: ";
cin>>key;
p=ternarySearch(l,r,key,a);
if(p==1)
{
cout<<"ternarySearch: element "<<key<<" is found true";
}
else
{
cout<<"ternarySearch: element "<<key<<" is found false";
}
cout<<"\nDo you want to continue(Y/N)? ";
cin>>response;
}
}

Screenshot of the Code:

Output:

Kindly comment below for any further queries.