### Binary Search in Multi Dimensional Vector

HI Folks, Is there any option to apply binary_search algorithm for multidimesional (2D) Vector ?
How are the elements sorted?
the elements are sorted by ascending order. Sorting type is string.
If they are stored in ascending order, then why not put them in a 1D vector?
Would you mind giving a sample vector, please?
Is there any option to apply binary_search algorithm for multidimesional (2D) Vector ?

If there are no empty vectors in the 2D vector:

 ``123456789`` ``````template < typename T, typename V > bool binary_search( const std::vector< std::vector >& outer, const V& v ) { static const auto lt = [] ( const std::vector& seq, const T& v ) { assert( !seq.empty() ) ; return seq.back() < v ; }; const auto iter = std::lower_bound( outer.begin(), outer.end(), v, lt ) ; return iter != outer.end() && std::binary_search( iter->begin(), iter->end(), v ) ; }``````

http://coliru.stacked-crooked.com/a/6e42d335c80b7676
I have tried the below code for binary search program to find at a specific column.
 ``1234567891011121314151617181920212223242526272829303132`` ``````class BINARY_ON { public: explicit BINARY_ON(int column,string fCol) :m_column(column),fColType(fCol) {} bool operator()(const string& lhs,const vector& rhs) { if(fColType=="number") return atoi(lhs.c_str()) < atoi(rhs[m_column].c_str()); else if(fColType=="date") return PPCheckTwoDate(lhs, rhs[m_column])<0; else return lhs < rhs[m_column]; } private: int m_column; string fColType; }; int main () { vector> table_data; // Vector Data Insert BINARY_ON compare_column(4,"date"); if (std::binary_search (table_data.begin(), table_data.end(), "01051996", compare_column)) std::cout << "found!\n"; else std::cout << "not found.\n"; }``````

I got the below errors.

 /usr/include/c++/4.6/bits/stl_algo.h:2416:4: error: no match for call to ‘(PPBINARY_ON) (std::vector >&, const char [9])’ note: bool PPBINARY_ON::operator()(const string&, const std::vector >&) note: no known conversion for argument 1 from ‘std::vector >’ to ‘const string& {aka const std::basic_string&}’

So I changed the PPBINARY_ON::operator() function definition as
bool operator()(const vector<string>& rhs, const string& lhs)

But now i got the error like this,
 /usr/include/c++/4.6/bits/stl_algo.h: In function ‘bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = __gnu_cxx::__normal_iterator >*, std::vector > > >, _Tp = char [9], _Compare = BINARY_ON]’: binarysearch.cpp:17:86: instantiated from here /usr/include/c++/4.6/bits/stl_algo.h:2714:56: error: no match for call to ‘(BINARY_ON) (const char [9], std::vector >&)’ note: bool BINARY_ON::operator()(const std::vector >&, const string&) note: no known conversion for argument 1 from ‘const char [9]’ to ‘const std::vector >&’

What is the error in it ? Did i use the binary search STL function correctly ?
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354`` ``````#include #include #include #include struct compare_cols { constexpr compare_cols( std::size_t c ) : col(c) {} using row_type = std::vector ; // binary predicate for sort bool operator() ( const row_type& a, const row_type& b ) const { if( a.size() < col ) return b.size() >= col ; else if( b.size() < col ) return false ; else return a[col] < b[col] ; } // binary predicate for string < vector bool operator() ( const std::string& str, const row_type& row ) const { if( row.size() < col ) return false ; else return str < row[col] ; } // binary predicate for vector < string bool operator() ( const row_type& row, const std::string& str ) const { if( row.size() < col ) return true ; else return row[col] < str ; } const std::size_t col ; }; int main() { std::vector< std::vector > v2d { { "zero", "ten", "twenty", "thirty" }, { "one", "fifteen", "twentythree", "thirtyeight" }, { "five", "thirteen", "twentynine", "thirtytwo" }, { "seven", "seventeen", "twentyseven", "thirtyseven" } }; compare_cols comp2(2) ; // compare strings in col two std::sort( std::begin(v2d), std::end(v2d), comp2 ) ; // sort on col two // binary search for string in col2 on sequence sorted on col 2 bool found = std::binary_search( std::begin(v2d), std::end(v2d), "twentythree", comp2 ) ; std::cout << "found? " << std::boolalpha << found << '\n' ; }``````

http://coliru.stacked-crooked.com/a/2e8fa75be767ce79
Your code is working fine. But It is not working for upper_bound and lower_bound algorithms.

I tried like this below.
` bool found = std::lower_bound( v2d.begin(), v2d.end(), "01011991", comp2 ) ;`

I got the below error.
 error: cannot convert ‘__gnu_cxx::__normal_iterator >*, std::vector > > >’ to ‘bool’ in initialization
> error: cannot convert '....' to ‘bool’ in initialization

std::upper_bound() and std::lower_bound() return iterators.
And std::equal_range() returns a pair of the two iterators.

http://coliru.stacked-crooked.com/a/3ea5f7e54a2a98f6
Topic archived. No new replies allowed.