1
\$\begingroup\$

This post is follow up of this, suggested by @loki-astari which can be found here.

Any further improvement is welcome.

Binary_Search.h

#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H

template<typename RandomIt, typename T>
RandomIt binary_search(RandomIt begin, RandomIt end, const T& key);

#endif // BINARY_SEARCH_H

Binary_Search.cpp

#include <iostream>
#include <vector>
#include "Binary_Search.h"

/* search a key in an array using binary search */
template<typename RandomIt, typename T>
RandomIt binary_search(RandomIt begin, RandomIt end, const T& key)
{
    RandomIt save_end = end;

    while ( begin <= end )
    {
        // find the middle iterator
        auto range = std::distance(begin, end);
        RandomIt mid = begin;
        std::advance(mid, range / 2);

        if ( *mid == key ) // key found
        {
            return mid;
        }
        else if ( *mid > key ) // key may be on the left half
        {
            end = mid;
            std::advance(end, -1);
        }
        else if ( *mid < key ) // key may be on the right half
        {
            begin = mid;
            std::advance(begin, 1);
        }
    }

    // key not found
    return save_end;
}

int main()
{
    std::vector<int> vec = {1, 7, 9, 10, 28, 28, 36, 49, 68, 99};


    for (auto v : vec)
    {
        if ( binary_search(vec.begin(), vec.end(), v) != vec.end() )
        {
            std::cout << v << " is present" << std::endl;
        }
        else
        {
            std::cout << v << " is not present" << std::endl;
        }
    }

    std::vector<int> vec1 = {-1, 2, 3, 12, 23, 50, 90, 98, 100};
    for (auto v : vec1)
    {
        if ( binary_search(vec.begin(), vec.end(), v) != vec.end() )
        {
            std::cout << v << " is present" << std::endl;
        }
        else
        {
            std::cout << v << " is not present" << std::endl;
        }
    }
    return 0;
}
\$\endgroup\$
3
  • \$\begingroup\$ There is a very big flaw here: templates are header only. Definition of the binary search should be in the header where it is declared. \$\endgroup\$ Commented Jan 29, 2017 at 16:01
  • \$\begingroup\$ But header files only contains declarations to keep it clean and simple so as to make it more readable. It shouldn't contain definition. And it isn't giving any compile time error also \$\endgroup\$ Commented Jan 31, 2017 at 14:58
  • \$\begingroup\$ Try to put definition of the binary search into different cpp file, and let the main to just include the header and contain only main. Linker will complain about undefined symbols. There is actually SO question about it, link. \$\endgroup\$ Commented Jan 31, 2017 at 17:00

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.