wyszukiwanie binarne

Question

Czy można za pomocą algorytmu wyszukiwania binarnego wyszukiwać zmienną typu string w tablicy obiektów?

Algorytmy wyszukujące zajmują się liczbami, więc czy trzeba zamienić stringa np na inta?

Answer 1

Tak, można.

Algorytm binary_search przeszukuje posortowany kontener porównując obiekty za pomocą operatora <, którym bez problemu można porównać 2 stringi.

vector<string> vecOfStr{"adam", "ewa", "zbigniew", "stonoga"};
//sortowanie
sort(vecOfStr.begin(), vecOfStr.end());
//wyszukiwanie binarne
bool found = binary_search(vecOfStr.begin(), vecOfStr.end(), "ewa");
//wyświetlenie czy znaleziono
cout << (found?"znaleziono":"nie znaleziono") << endl;

 

Comments

Ok, a czy da się posortować tablicę obiektów według zmiennej?  

Chodzi mi o to, że każdy obiekt w tablicy ma swoje imię i jest to określone wskaźnikiem

przykład:   tablica_pies[licznik_pies] -> imie;

Chcę posortować te obiekty tak, żeby występowały w kolejności alfabetycznej względem zmiennej imie.

Czy da się to zrobić?

---

Rozumiem, że masz klase Pies i chcesz posortować tablice obiektów Pies alfabetycznie względem imienia, tak? W takim wypadku żeby móc korzystać z funkcji sort z <algorithm>, musisz przeciążyć operator < w klasie Pies, lub napisać własny predykat porównujący 2 psy.

W klasie Pies przeciążasz operator <

bool operator<(const Pies& other) const {
        return m_imie < other.imie();
}

I sortowanie następuje poprzez wywołanie funkcji

sort(początek_zakresu, koniec_zakresu);

W przypadku używania predykatu, jako trzeci argument funkcji sort podajesz jego nazwę. Przykładowy predykat do sortowania psów alfabetycznie względem imienia:

bool compare(const Pies& p1, const Pies& p2)
{
    return p1.imie() < p2.imie();
}

I sortujesz:

sort(początek_zakresu, koniec_zakresu, compare);