hjälp med binär sökning!!
Hej fick i uppgift att göra ett program med olika familj medlemmar som sen skulle sortera de i slutet.
Men nu ska jag lägga till en funktion för binär sökning som söker efter ålder i en personvektor. Funktionen skall ha en rekursiv(anropa sig själv) algoritm.
titta på funktionen ( int binarySearch) och hjälp mig få in den i main funktionen att ha en rekursiv algoritm
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Person // Klass: Innehåller en person
{
public:
string namn;
int alder;
void SkrivUt()
{
cout << "Namn: " << namn <<", "<< alder << " \x8Fr." << endl; // Talar om vad som ska skrivas ut
}
void setInfo(string _namn, int _alder) // Sätter den info som krävs
{
namn = _namn;
alder = _alder;
}
};
int linsok(Person p[], int n, int a) // Linjär sökning av ålder
{
for (int i = 0; i < n; i++) // Går igenom hela listan
{
if (p[i].alder == a) // Hittar det vi söker efter eller...
{
return i;
}
}
return -1; // ... så hittas inte personen
};
void bubblesort(Person p[], int n)
{
int i = 0;
for ( i = 0; i < n; i++) // Yttre loop söker igenom hela listan
{
int nrLeft = n - i; // Inre loop, element för element
for (int j = 0; j < nrLeft; j++)
{
if (p[j].alder > p[j+1].alder) // Jämför elementen
{
// Byter plats
Person temp = p[j];
p[j] = p[j+1];
p[j+1] = temp;
}
}
}
}
int binarySearch(Person p[], int lowerIndex, int upperIndex, int age)
{
int middleIndex = (lowerIndex + upperIndex)/2;
if (p[middleIndex].alder == age)
return middleIndex; //Ålder hittad //Hur får jag denna funktionen att ha en rekursiv algoritm
else if (lowerIndex == upperIndex)
return -1; //Ålder inte hittad
else if (p[middleIndex].alder > age)
return binarySearch(p, lowerIndex, middleIndex-1, age); //Titta på nedre halvan
else if (p[middleIndex].alder < age)
return binarySearch(p, middleIndex+1, upperIndex, age); //Titta på övre halvan
}
int main() {
//Skapar en lista med personer - namn/ålder
cout << "-- Osorterad lista --" << endl << endl; // Skriver ut titel
Person familj[4];
familj[0].setInfo("Noah", 5); // Person 1. Börja från 0!
familj[0].SkrivUt(); // Anropar void SkrivUt()
familj[1].setInfo("Mike", 32);
familj[1].SkrivUt();
familj[2].setInfo("Eva", 33);
familj[2].SkrivUt();
familj[3].setInfo("Danin", 12);
familj[3].SkrivUt();
cout << endl << "-- Sorterad lista --" << endl << endl; // Skriver ut titel
bubblesort(familj, 3); //Anropar funktionen bubblesort för att sortera vektorn Familj.
for (int i = 0; i < 4; i++) //Den sorterade listan skrivs ut
cout << "Namn: " << familj[i].namn << ", " << familj[i].alder << " \x8Fr." << endl; // Berättar vad som ska skrivas ut
int index = linsok(familj, 4, 5); //Söker efter en viss person i vektorn Familj som innehåller 4 element och ska vara 5 år gammal
if (index == -1)
cout << "Personen hittas ej!"; // Antingen hittas inte personen eller...
else
cout << endl << familj[index].namn << " finns p\x86 plats " << index << " i listan."; // ... så hittar programmet personen och info skrivs ut.
cin.get();
return 0;
}