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

Question

HELP!!!

1. 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'm not sure if i would do the same thing as i would do if the list was unsorted and just need to be pushed in the right direction)

2. Write a client function that merges two of these Sorted Lists together. (I'm not even sure where to start for this one)

Explanation / Answer

1)

// I have used binary search to search item

bool IsThere(ItemType item){
int low = 0;
int high = sz -1; //here sz is size of array, since you have not given code
                   // of SortedType class, so I an assuming thant array name is 'a'
                   // please replace array name with what you have declared in class

while(low <= high) {
int mid = (low+high)/2;

if(item < a[mid])
high = mid - 1;
else if(item > a[mid])
low = mid + 1;
else
return a[mid];
}
return -1;
   }

2).

void mergeTwoSortedArrays(const int a1[], const int a2[], int mergedArray[], int n) {

int i = 0;
int j = 0;
int k = 0;

// Iterate and compare two input arrays until at least one of them reaches to boundary.
while (i < n && j < n) {
if (a1[i] < a2[j]) {
mergedArray[k++] = a1[i++];
}
else if (a1[i] > a2[j]) {
mergedArray[k++] = a2[j++];
}
else if (a1[i] == a2[j]) {
mergedArray[k++] = a1[i++];
mergedArray[k++] = a2[j++];
}
}

// Copy the remaining items from the other array, without comparison until, boundary.
while (i < n) mergedArray[k++] = a1[i++];
while (j < n) mergedArray[k++] = a2[j++];

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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