Binarne wyszukiwanie elementu w wektorze w celu usunięcia...

Witam,
Mam następujący problem w STL: chcę wyszukać pewien element wektora, a następnie go usunąć. Ponieważ wektor jest posortowany chcę wykorzystać wyszukiwanie binarne (lub inne, które wykorzysta to uporządkowanie).

Wiem, że w nagłówku <algorithm> znajduje się funkcja binary_search, ale zwraca ona czy element znajduje się w kontenerze lub nie, a ja potrzebuje indeks na jakiej pozycji się on znajduje. Mam funkcje:
http://www.cplusplus.com/reference/algorithm/adjacent_find/
ale nie wykorzystuje ona uporządkowania tablicy.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Dane {
    int indeks;
    int wartosc;
    Dane(int indeks, int wartosc) : indeks(indeks), wartosc(wartosc) { }
    void wyswietl() {
        cout << indeks << " " << wartosc << "\n";
    }
};

bool comparator(Dane a, Dane b) {
    return a.indeks < b.indeks;
}

int main()
{
    vector<Dane> baza;

    /*
     *  Pobierz dane
     */
    int in, wa;
    for(int i = 0; i < 4; ++i) {
        cout << "Podaj indeks: ";
        cin >> in;
        cout << "Podaj wartosc: ";
        cin >> wa;
        baza.push_back(Dane(in, wa));
    }

    /*
     *  Posortuj dane
     */
    sort(baza.begin(), baza.end(), comparator);
    cout << "Pobrano" << "\n";
    for(int i = 0; i < baza.size(); ++i) baza[i].wyswietl();

    /*
     *  Wyszukiwanie binarne: znajdz jego indeks
     */

    /*
     *  Usun znaleziony element
     */

    /*
     *  Wyswietl rezultat
     */
     for(int i = 0; i < baza.size(); ++i) baza[i].wyswietl();

    return 0;
}

Jak można to zrobić najprościej?

A tak po prostu nie mozna do tej klasy dodac:

bool operator==(const Dane& x) {
    return this->indeks == x.indeks && this->wartosc == x.wartosc;
}

i uzyc:
http://www.cplusplus.com/reference/algorithm/find/

Chyba nie wykorzysta to posortowania mojej tablicy? A na tym mi najbardziej zależy.

Jest rozwiązanie na to w stl'u: http://en.cppreference.com/w/cpp/algorithm
Konkretnie poczytaj o equal_range, lower_bound i upper_bound (sekcja "Binary search operations (on sorted ranges)").

W zasadzie nawet odpowiedź na twoje pytanie znajduje się na cppreference.com - binary_search. Dokładniej to przejrzyj sekcję "Possible implementation", która pokazuje jak możesz zrobić to co chcesz. Oczywiście sugerowana implementacja wykorzystuje algorytmy, o których wspomniał @byku_guzio .

Mam ten kodzik, chodzi za pewne o funkcje:

template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value);
    return (first != last && !(comp(value, *first));
}

Probuje zrozumiec jej dzialanie, bo nie znam sie na szablonach. Pierwsza linia znajduje wartosc nie mniejsza niz poszukiwana. Na podstawie tej wiedzy mozemy stwierdzic czy operacja sie udala czy nie.

Rozumiem, ze *first powoduje wyciagniecie wartosci z iteratora (dziwny wskaznik, chyba przeciazenie?). Ja z tego *first chcialbym wyciagnac indeks w wektorze i zwrocic int.

Skoro chcesz usunac "wyciagniety" obiekt to wystarczy zwrocic iterator i uzyc funkcji erase.
Natomiast sam iterator nie ma wiedzy na ktory indeks wskazuje.

Ok, dziekuje, sporo mi wyjasniliscie, w wolnej chwili ubiore to w kod.