Permalänk
Medlem

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

Permalänk
Medlem

Det enda felet på din binSearch jag kan se är att person borde vara Person med stort P i parameter listan. I övrigt borde den fungera, vad har du för problem med den ?

Permalänk
Medlem

@furbel:

p är ändrad till P. Programmet ska ha en funktion för binär sökning som söker efter
ålder i en personvektor. Funktionen skall ha en rekursiv algoritm, dvs. den skall
anropa sig själv.
Den binära sökningen förutsätter att vektorn är sorterad.
sen skall jag ha en kod i huvudprogrammet för att testa min funktion.

Permalänk
Medlem

Din(?) binarySearch funktion har redan en rekursiv algoritm. Du söker i ena eller andra halvan eller avslutar med basvillkoret som är att antingen hittas det du söker efter eller så möts index utan att något hittats och då returneras -1

En rekursiv algoritm har alltid ett basvillkor som avslutar och ett eller flera rekursiva anrop. Allt måste inte vara anrop till samma funktion utan det är helt korrekt som det är om det var det som var frågetecknet.

Återstår bara att anropa den korrekt i main
int index = binarySearch(familj, 0, 4, 5); // Söker efter 5