jsam
8/26/2012 - 12:07 PM

Binary Search of words

Binary Search of words

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool BinSearch( string P[], string K, int i, int j ) 
{
  if ( j - i <= 0 )
    if ( i == j && P[ i ] == K ) 
      return true;
    else
      return false;
  else 
  {
    int k = ( i + j ) / 2;
    if ( P[ k ] > K )
      return BinSearch( P, K, i, k - 1 );
    if ( P[ k ] == K )
      return true;
    if ( P[ k ] < K )
      return BinSearch( P, K, k + 1, j );
  }
}
int main()
{
  int N, k;
  string K;
  vector< string > A;
  do 
  {
    cout << "N = ";
    cin >> N;
  } while ( N < 2 && N > 1000 );
  for ( int i = 0; i < N; i++ ) 
  {
    cout << "array[" << i 
	 << "] = ";
    cin >> K;
    A.push_back( K );
  }
  cout << "search: ";
  cin >> K;
  // string* arr = &A[ 0 ]; ....konverzija vectora u string arr
  if ( BinSearch( &A[ 0 ], K, 0, N - 1 ) )
    cout << "festa =)) "; // rijec pronadena
  else 
    cout << "nema feste =("; // rijec nije pronadena :(
  cout << endl;

  // ak si na windowzima stavi tu onu glupost system("pause");
  return 0;
}