Question

Exercise 3: Searching Applications

Design and implement an algorithm that determines whether or not a given array of integers, list1, is completely contained within another given array of integers, list2. Consider two different scenarios: (1) Both arrays are unsorted and (2) both arrays are sorted and write functions unsortedSearch and sortedSearch for (1) and (2), respectively. Your algorithm for (2) is expected to be more efficient than the one for (1).

Please Answer in c++ and show the algorithm working

Answer 1

Program:

The code uses binary and linear search and the code is given below

#include <iostream>
using namespace std;
bool binarysearch(int arr[],int size,int key)
{
int low=0;
int high=size-1;
while(low<=high)
{
int mid=(low+high)/2;
if(arr[mid]==key)
return true;
else if (arr[mid]>key)
high=mid-1;
else
low=mid+1;
}
return false;
}
bool linearsearch(int arr[],int size,int key)
{
for (int i=0;i<size;i++)
if(arr[i]==key)
return true;
return false;
}
bool findSorted(int arr1[],int arr2[],int size1,int size2)
{
//arr1 is the larger array of size 1
//arr2 is the smaller array which is to be checked whether it is in arr1
for(int i=0;i<size2;i++)
{
if(binarysearch(arr1,size1,arr2[i])==false)
return false;
}
return true;
}
bool findUnSorted(int arr1[],int arr2[],int size1,int size2)
{
for(int i=0;i<size2;i++)
{
if(linearsearch(arr1,size1,arr2[i])==false)
return false;
}
return true;
}
int main()
{
int arr[]={0,1,2,3,4,5};
int arr1[]={68,6,46,8};
int arr2[]={5,2,4,1};
if(findSorted(arr,arr2,6,4))
cout<<"Yes\n";
else
cout<<"No\n";
if(findSorted(arr,arr1,6,4))
cout<<"Yes\n";
else
cout<<"No\n";

return 0;
}

Output:

input Yes No -..Program finished with exit code 0 Press ENTER to exit console.|