Rechercher une sous-liste dans une liste à l'aide d'une recherche binaire - c ++, algorithme, recherche binaire

Je dois utiliser pour voir si smallList est une sous-liste de bigList en vérifiant que les valeurs de smallList apparaissent dans le même ordre que dans bigList. Les éléments doivent également correspondre séquentiellement

int bigList[] = {1,2,3,4,5,6,7,8,9};
int smallList[] = {3,4,5,6};

Algortithme binaire:

bool binarySearch(int x[],int list[],int first, int last)
{
bool yes=true;
bool no=false;
int mid=(first+last)/2;
if(x[last]>list[mid])
{
binarySearch(x,list,mid,last);
}
else if (x[last]<list[mid])
{
binarySearch(x,list,first,mid);
}
else if (x[last]==list[mid])
{
return true;
}
else
{
return false;
}
}

J'ai besoin de savoir comment je peux utiliser / modifier l'algorithme ci-dessus pour vérifier que smallList est une sous-liste de bigList. Je dois utiliser l'algorithme pour comprendre cela. Lien vers le problème: https://docs.google.com/document/d/12pWWQo66-P-CMWoFH0HPWy09ws4LccGay2pKsv0XWlo/edit?usp=sharing

Réponses:

La bibliothèque standard contient std::includes et std::search algorithmes à ces fins:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ios>

int main()
{
int bigList[] = {1,2,3,4,5,6,7,8,9};
int smallList[] = {3,4,5,6};

std::cout << std::boolalpha;
std::cout << std::includes(
std::begin(bigList), std::end(bigList),
std::begin(smallList), std::end(smallList)
);

std::cout << (std::search(
std::begin(bigList), std::end(bigList),
std::begin(smallList), std::end(smallList)
) != std::end(bigList));
}

Exemple en direct qui imprime truetrue.

std::includes vérifie si tous les éléments de smallList sont contenus dans bigList, et std::search vérifie si smallList est une sous-séquence appropriée de bigList (et retourne l'itérateur final s'il ne l'est pas).