Question

1. 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 following code shows the execution of ternary search to find an element in the list.

Code:

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

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

int main()
{
int accounts,i,l,r,key,p=0;
char response='Y';
cout<<"Enter number of accounts: ";
cin>>accounts;
int acc[accounts];
l=0;
r=accounts-1;
cout<<"Accounts are:\n";
for(i=0;i<accounts;i++)
{
cout<<"["<<i<<"] ";
cin>>acc[i];
}
sort(acc,acc+accounts);
cout<<"\nSorted Accounts are: ";
for(i=0;i<accounts;i++)
{
cout<<"\n["<<i<<"] "<<acc[i];
}
do
{
cout<<"\nEnter account to search: ";
cin>>key;
p=ternarySearch(l,r,key,acc);
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;
}while(response=='Y'||response=='y');
}

Code Screenshot:

Output Screenshot: