How to implement the binary_search() in C++

[Garett]

I am studying in the BSC-CS. I can not have the much more knowledge of the C++ language. I also can not know about the functions of the C++ language. So, I would like to know about the binary_search() of the C++ language. I also would like to know about how the binary_search() function can be implemented in the C++ programming. I hope anyone can has the answer for me and guides me about the binary_search() function.

[MindSpace]

The binary_search() function can be used in the C++ language to check that if value can be exists in the sorted array. The binary_search() function can returns the true value if an element can be in the range [fst,lst) can be similar to value and false otherwise. The following can be the syntax of the binary_search() function of the C++ language :

template <class FrwrdItrtr, class S>
  bool binary_search ( FrwrdItrtr fst, FrwrdItrtr lst,
                       const S& val );

[Modifier]

The following can be the parameters of the binary_search() function of the C++ language as :
1. val : This parameter of the binary_search() function can contains the value of an element to search for.
2. fst, lst : These parameter of the binary_search() function can contains forward iterators to the final and starting positions of the given specified sequence that can be searched. The range used can be [fst,lst).

[Praetor]

I think you can have to go though the following code of lines that can describes you what is the use and how to implement the binary_search() function in the C++ programming :

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool mfunction (int i,int j) 
{
 return (i<j); 
}
int main ()
 {
  int mints[] = {1,2,3,4,5,4,3,2,1};
  wector<int> w(mints,mints+9);               
  sort (w.begin(), w.end());
  cout << "looking for a 3... ";
  if (binary_search (w.begin(), w.end(), 3))
    cout << "found!\n"; else cout << "not found.\n";
  sort (w.begin(), w.end(), mfunction);
  cout << "looking for a 6... ";
  if (binary_search (w.begin(), w.end(), 6, mfunction))
    cout << "found!\n"; else cout << "not found.\n";
  return 0;
}

Output:

looking for a 3... found!
looking for a 6... not found.

[Katty]

The binary_search() function can searches from the beginning to an end for the value. The elements that can be in between beginning and end that can be searched could be in an order of ascending as can be defined by the "<" an operator. You can have noticed that a binary_search() function can not work unless an elements has bee searched can be in an order. If the value can be found, binary_search() function can returns true value else returns the false value. If the comparison variable can be specified then the binary_search() function can be used to compare an elements. The binary_search() function can runs in the logarithmic time.

[kelfro]

PROGRAM :

#include <list>
#include <vector>
#include <algorithm>
#include <iostream>
bool mod_lesser ( int elm1, int elm2 )
{
   if (elm1 < 0)
      elm1 = - elm1;
   if (elm2 < 0)
      elm2 = - elm2;
   return elm1 < elm2;
}
int main( )
{
   using namespace std;
   list <int> L;
   list <int>::Itrator Itr;
   bool b1, b2;
   L.pshback( 50 );
   L.pshback( 10 );
   L.pshback( 30 );
   L.pshback( 20 );
   L.pshback( 25 );
   L.pshback( 5 );
   L.sort( );
   cout << "L = ( " ;
   for ( Itr = L.begin( ) ; Itr != L.end( ) ; Itr++ )
      cout << *Itr << " ";
   cout << ")" << endl;
   b1 = binary_search( L.begin( ), L.end( ), 10 );
   if  ( b1 )
      cout << "There is an element in list L with a value equal to 10."
           << endl;
   else
      cout << "There is no element in list L with a value equal to 10."
           << endl;
   L.sort ( greater<int> ( ) );
   b2 = binary_search( L.begin( ), L.end( ), 10 , greater<int> ( ) );
   if  ( b2 )
      cout << "There is an element in list L with a value equivalent to 10 "
           << "under greater than." << endl;
   else
      cout << "No element in list L with a value equivalent to 10 "
           << "under greater than." << endl;
   vector <int> K1;
   vector <int>::Itrator Itr1;
   int i;
   for ( i = -2 ; i <= 4 ; i++ )
   {
      K1.pshback( i );
   }
   sort ( K1.begin ( ) , K1.end ( ) , mod_lesser );
   cout << "Ordered under mod_lesser, vector K1 = ( " ;
   for ( Itr1 = K1.begin( ) ; Itr1 != K1.end( ) ; Itr1++ )
      cout << *Itr1 << " ";
   cout << ")" << endl;
   bool b3 = binary_search( K1.begin( ), K1.end( ), -3 , mod_lesser );
   if ( b3 )
      cout << "There is an element with a value equivalent to -3 "
           << "under mod_lesser." << endl;
   else
      cout << "There is not an element with a value equivalent to -3 "
           << "under mod_lesser." << endl;
}

Output

L = ( 5 10 20 25 30 50 )
There is an element in list L with a value equal to 10.
There is an element in list L with a value equivalent to 10 under greater than.
Ordered under mod_lesser, vector K1 = ( 0 -1 1 -2 2 3 4 )
There is an element with a value equivalent to -3 under mod_lesser.