Finde die Unterliste in einer Liste mit der binären Suche - c ++, Algorithmus, binäre Suche

Ich muss verwenden, um zu sehen, ob smallList eine Unterliste von bigList ist, indem ich prüfe, ob die Werte von smallList in derselben Reihenfolge in bigList angezeigt werden. Die Elemente müssen auch sequentiell übereinstimmen

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

Binärer Algortithmus:

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;
}
}

Ich muss wissen, wie ich den obigen Algorithmus verwenden / modifizieren kann, um zu prüfen, ob smallList eine Unterliste von bigList ist. Ich MUSS den Algorithmus verwenden, um das herauszufinden. Link zum Problem: https://docs.google.com/document/d/12pWWQo66-P-CMWoFH0HPWy09ws4LccGay2pKsv0XWlo/edit?usp=sharing

Antworten:

Die Standard Library enthält std::includes und std::search Algorithmen für solche Zwecke:

#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));
}

Live Beispiel das druckt truetrue.

std::includes prüft ob alle Elemente aus smallList sind in enthalten bigList, und std::search prüft ob smallList ist eine richtige Folge von bigList (und gibt den End-Iterator zurück, wenn es nicht "t" ist).