mario::konrad
programming / C++ / sailing / nerd stuff
Algorithm: Binary Search
© 2005 / Mario Konrad

Description

TODO:DESCRIPTION

C++

search_binary.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <vector>

template <typename T, class RandomAccessIterator>
RandomAccessIterator search_binary(
    RandomAccessIterator begin,
    RandomAccessIterator end,
    T const & element)
{
    RandomAccessIterator i = end;
    while (begin != i) {
        RandomAccessIterator m = begin + (i - begin) / 2;
        if (*m == element)
            return m;
        if (m == begin)
            return end;

        if (*m < element) {
            begin = m;
        } else {
            i = m;
        }
    }
    return end;
}

int main(int, char **)
{
    std::vector<int> v{ 60, 50, 10, 80, 0, 40, 90, 20, 70, 30, 10 };
    std::sort(v.begin(), v.end());
    auto i = search_binary(v.begin(), v.end(), 60);

    if (i == v.end()) {
        std::cout << "element not found" << std::endl;
    } else {
        std::cout << "element found " << *i << " at index "
            << i - v.begin() << std::endl;
    }

    return 0;
}