// s4.cpp
#include <iostream>
using namespace std;


class array {
private:
  int *data;
  int size;
public:
  array( int n ) : size( n ) { data = new int[n]; }
  void set( int x, int v ) { data[x] = v; }
  int getSize() { return size; }
  int getItem( int x ) { return data[x]; }
  void print( int x );
  int linearSearch( int key );
  int linearSearchSorted( int key );
  int binarySearch( int key );
  int recursiveBinarySearch( int key, int lo, int hi, int count );
}; // end of class array


void array::print( int x ) {
  if ( x < size ) {
    cout << data[x] << " ";
    print( x+1 );
  }
  else {
    cout << endl;
  }
} // end of array::print()


int array::linearSearch( int key ) {
  int count = 0;
  for ( int i=0; i<getSize(); i++ ) {
    count++;
    if ( key == getItem( i )) {
      cout << "count=" << count << endl;
      return( i );
    }
  } // end for i
  cout << "count=" << count << endl;
  return( -1 );
} // end of array::linearSearch()


int array::linearSearchSorted( int key ) {
  int count = 0;
  for ( int i=0; i<getSize(); i++ ) {
    count++;
    if ( key == getItem( i )) {
      cout << "count=" << count << endl;
      return( i );
    }
    else if ( key < getItem( i )) {
      cout << "count=" << count << endl;
      return( -1 );
    }
  } // end for i
  cout << "count=" << count << endl;
  return( -1 );
} // end of array::linearSearchSorted()


int array::binarySearch( int key ) {
  int count = 0;
  int lo = 0, hi = getSize()-1, mid;
  while ( lo <= hi ) {
    count++;
    mid = ( lo + hi ) / 2;
    if ( key == getItem( mid )) {
      cout << "count=" << count << endl;
      return( mid );
    }
    else if ( key < getItem( mid )) {
      hi = mid - 1;
    }
    else {
      lo = mid + 1;
    }
  } // end while
  cout << "count=" << count << endl;
  return( -1 );
} // end of array::binarySearch()


int array::recursiveBinarySearch( int key, int lo, int hi, int count ) {
  if ( lo <= hi ) {
    int mid = ( lo + hi ) / 2;
    if ( key == getItem( mid )) {
      cout << "count=" << count << endl;
      return( mid );
    }
    else if ( key < getItem( mid )) {
      return( recursiveBinarySearch( key, lo, mid-1, count+1 ));
    }
    else {
      return( recursiveBinarySearch( key, mid+1, hi, count+1 ));
    }
  }
  else {
    cout << "count=" << count << endl;
    return( -1 );
  }
} // end of array::recursiveBinarySearch()



int main() {
  int x;
  array A( 5 );

  for ( int i=0; i<5; i++ )
    A.set( i,i*10 );
  cout << "here is the array: ";
  A.print( 0 );

  cout << "looking for item 30 using linearSearch()...";
  x = A.linearSearch( 30 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;
  cout << "looking for item 15 using linearSearch()...";
  x = A.linearSearch( 15 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;

  cout << "looking for item 30 using linearSearchSorted()...";
  x = A.linearSearchSorted( 30 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;
  cout << "looking for item 15 using linearSearchSorted()...";
  x = A.linearSearchSorted( 15 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;

  cout << "looking for item 30 using binarySearch()...";
  x = A.binarySearch( 30 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;
  cout << "looking for item 15 using binarySearch()...";
  x = A.binarySearch( 15 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;

  cout << "looking for item 30 using recursiveBinarySearch()...";
  x = A.recursiveBinarySearch( 30, 0, A.getSize()-1, 1 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;
  cout << "looking for item 15 using recursiveBinarySearch()...";
  x = A.recursiveBinarySearch( 15, 0, A.getSize()-1, 1 );
  if ( x == -1 )
    cout << "not found\n";
  else
    cout << "found at location: " << x << endl;

} // end of main() method