HELP!! Add a function to the SortedType class with the following signature: bool

Question

HELP!!

Add a function to the SortedType class with the following signature: bool IsThere(ItemType item) const; Since this is an array backed data structure, a binary search algorithm would work well here (so use one). Also, in the comments for this function, describe the function in terms of Big-O.

I also need to write a test function in main so how would i do that?

HERE IS MY CLASS FILE FOR SORTED TYPE

ALSO, MAX_ITEMS = 5

#include "SortedType.h"

SortedType::SortedType()
{
length = 0;
}

void SortedType::MakeEmpty()
{
length = 0;
}

bool SortedType::IsFull() const
{
return (length == MAX_ITEMS);
}

int SortedType::GetLength() const
{
return length;
}

ItemType SortedType::GetItem(ItemType item, bool& found)
{
int midPoint;
int first = 0;
int last = length - 1;

bool moreToSearch = first <= last;
found = false;
while (moreToSearch && !found)
{
midPoint = ( first + last) / 2;
switch (item.ComparedTo(info[midPoint]))
{
case LESS : last = midPoint - 1;
moreToSearch = first <= last;
break;
case GREATER : first = midPoint + 1;
moreToSearch = first <= last;
break;
case EQUAL : found = true;
item = info[midPoint];
break;
}
}
return item;
}

void SortedType::DeleteItem(ItemType item)
{
int location = 0;

while (item.ComparedTo(info[location]) != EQUAL)
location++;
for (int index = location + 1; index < length; index++)
info[index - 1] = info[index];
length--;
}

void SortedType::PutItem(ItemType item)
{
bool moreToSearch;
int location = 0;

moreToSearch = (location < length);
while (moreToSearch)
{
switch (item.ComparedTo(info[location]))
{
case LESS : moreToSearch = false;
break;
case GREATER : location++;
moreToSearch = (location < length);
break;
}
}
for (int index = length; index > location; index--)
info[index] = info[index - 1];
info[location] = item;
length++;
}

void SortedType::ResetList()
// Post: currentPos has been initialized.
{
currentPos = -1;
}

ItemType SortedType::GetNextItem()
// Post: item is current item.
// Current position has been updated.
{
currentPos++;
return info[currentPos];
}

Explanation / Answer

First include :

bool IsThere(ItemType item) const; in SortedType.h

Now find code:

#include "SortedType.h"

SortedType::SortedType()
{
length = 0;
}
void SortedType::MakeEmpty()
{
length = 0;
}

bool SortedType::IsFull() const
{
return (length == MAX_ITEMS);
}
int SortedType::GetLength() const
{
return length;
}
ItemType SortedType::GetItem(ItemType item, bool& found)
{
int midPoint;
int first = 0;
int last = length - 1;
bool moreToSearch = first <= last;
found = false;
while (moreToSearch && !found)
{
midPoint = ( first + last) / 2;
switch (item.ComparedTo(info[midPoint]))
{
case LESS : last = midPoint - 1;
moreToSearch = first <= last;
break;
case GREATER : first = midPoint + 1;
moreToSearch = first <= last;
break;
case EQUAL : found = true;
item = info[midPoint];
break;
}
}
return item;
}
void SortedType::DeleteItem(ItemType item)
{
int location = 0;
while (item.ComparedTo(info[location]) != EQUAL)
location++;
for (int index = location + 1; index < length; index++)
info[index - 1] = info[index];
length--;
}
void SortedType::PutItem(ItemType item)
{
bool moreToSearch;
int location = 0;
moreToSearch = (location < length);
while (moreToSearch)
{
switch (item.ComparedTo(info[location]))
{
case LESS : moreToSearch = false;
break;
case GREATER : location++;
moreToSearch = (location < length);
break;
}
}
for (int index = length; index > location; index--)
info[index] = info[index - 1];
info[location] = item;
length++;
}
void SortedType::ResetList()
// Post: currentPos has been initialized.
{
currentPos = -1;
}
ItemType SortedType::GetNextItem()
// Post: item is current item.
// Current position has been updated.
{
currentPos++;
return info[currentPos];
}
bool SortedType::IsThere(ItemType item){
   int mid,low=0,high=length-1;
   while(low<=high)
   {
       mid=(low+high)/2;
       if(item>info[mid])
           low=mid+1;
       else high(item<info[mid])
           high=mid-1;
       else
           return true;
   }
   return false;
   }

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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