Binary Search Algorithmus implementieren

Hallo,

hier ist mein Code:

template<typename Iterator>
Iterator binary_search(Iterator begin, Iterator end, const typename Iterator::value_type& what){
    if(std::distance(begin, end) < 1)
        return begin;
 
    for(Iterator mid, first = begin; begin <= end; ){
        std::size_t left_dist = std::distance(first, begin);
        mid = first + left_dist + std::distance(first + left_dist, end - 1) / 2;
 
        if(*mid == what)
            return mid;
 
        if(*mid > what)
            end = --mid;
        else
            begin = ++mid;
    }
 
    return end;
}

Aber es scheint nicht so sehr zu funktionieren und ich weiß nicht warum. Eigentlich hab ich mir die Beispiele im Netz alle angesehen, aber ich sehe nicht was ich anders falsch mach?

Hier ist mein Test-Code:

int main(){
    std::vector<unsigned> v{
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
        3445, 34556, 3455, 3474, 34554, 3454,
        2585, 48, 8548, 1885, 4685
    };
 
    for(unsigned x : v){
        auto it = binary_search(v.begin(), v.end(), x);
 
        if(it == v.end())
            std::cerr << x << " not found... :(\n";
        else
            std::cerr << x << " found! :D\n";
    }
}

Ich hab ne Liste mit Werten und suche sie mit dem Algorithmus alle der Reihe nach einmal ab. Aber tut nicht überall. Im Bereich von [1 - 10] irgendwie schon, aber ein paar Werte bleiben irgendwie aus...

Hier ist die Ausgabe vom Test-Code:

1 found! :D
2 found! :D
3 found! :D
4 found! :D
5 found! :D
6 found! :D
7 found! :D
8 found! :D
9 found! :D
10 found! :D
3445 found! :D
34556 not found... :(
3455 found! :D
3474 found! :D
34554 not found... :(
3454 found! :D
2585 found! :D
48 found! :D
8548 found! :D
1885 found! :D
4685 found! :D

EDIT: Und wofür brauch ich Binary Search eigentlich? Warum sollte man eine Liste auf diese Weise durchlaufen wollen? Irgendwelche Beispielserwähnungen?

RBS2

@JAMP sagte in Binary Search Algorithmus implementieren:

Aber es scheint nicht so sehr zu funktionieren und ich weiß nicht warum

Binary Search ist für sortierte Arrays. Dein Vector ist aber nur am Anfang sortiert. Nach der 34556 kommt wieder ein kleinerer Wert. Das könnte der Grund sein.

@RBS2, danke, das hat geholfen.

RBS2

@JAMP sagte in Binary Search Algorithmus implementieren:

@RBS2, danke, das hat geholfen.

Keine Ursache. Wenn du ein unsortiertes Array durchsuchen willst, bleibt nur stumpfes Abklappern der einzelnen Elemente in einer Schleife.

Finnegan

@JAMP sagte in Binary Search Algorithmus implementieren:

EDIT: Und wofür brauch ich Binary Search eigentlich? Warum sollte man eine Liste auf diese Weise durchlaufen wollen? Irgendwelche Beispielserwähnungen?

Die Binäre Suche liegt mit $\mathcal{O}(\log{}n)$ anstatt $\mathcal{O}(n)$ für die lineare Suche in einer effizienteren Komplexitätsklasse. Sie führt also im Schnitt in weniger Schritten zum Ergebnis und ist sogar im Vergleich zur Linearen Suche umso schneller, je mehr Elemente durchsucht werden müssen, da die Anzahl der notwendigen Verarbeitungsschritte bei dieser mit der Problemgröße wesentlich langsamer wächst.

Es ist allerdings wie bereits erwähnt erforderlich, dass die Elemente sortiert vorliegen - wenn das ohnehin schon der Fall ist, dann bietet sich es sich an, die Elemente auf diese Weise zu durchsuchen. Auch wenn man sehr viele Suchanfragen innerhalb eines weitgehend statischen Array durchführen will, kann es Sinn machen, dieses zunächst einmal zu sortieren und dann mit Binärer Suche zu arbeiten.

Liest sich sehr schön.