Interpolation search cpp program

Program to implement interpolation search

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

const int MAX=50;

class array

{ private:

          int arr[MAX];

          int count;

 public:

          array()

          {count=0;}

           void add(int);

          void display();

          int search(int);

          void sort();

};

//add new element to the array

void array::add(int item)

{        if(count<MAX)

          {        arr[count]=item;

                    count++;

          }

          else

                   cout<<"\nArray is full\n ";

}

//Display elements in the list

void array::display()

{        cout<< "\nThere are"<<count<<" elements in the list \n";

          cout<<"\n They are : \n";

          for(int i=0;i<count;i++)

                   cout<<arr[i]<<" ";

}

//Sort the array

void array::sort()

{        for(int i=0;i<count-1;i++)

                   for(int j=0;j<(count-i-1);j++)

                             if(arr[j]>arr[j+1])

                             {        int t=arr[j];

                                      arr[j]=arr[j+1];

                                      arr[j+1]=t;

                             }

          return;

}

//finds for given element in an array

int array::search(int num)

{        int mid,lower=0,upper=count-1;

          for(mid=lower+((upper-lower)*(num-arr[lower]))/(arr[upper]-arr[lower]);

                   lower<=upper;

          mid=lower+((upper-lower)*(num-arr[lower]))/(arr[upper]-arr[lower]))

          {        if(arr[mid]==num)

                             return mid;

                   if(arr[mid]>num)

                             upper=mid-1;

                   else

                             lower=mid+1;

          }

          return -1;

}

void main()

{        int element,n,i,c;

          array interpolation;

          while(1)

          {        clrscr();

                   cout<<"\nPerform the Interpolation Search";

                   cout<<"\n-------------------------------";

                   cout<<"\n1.Input data into the list";

                   cout<<"\n2.Display data in the list";

                   cout<<"\n3.Search an item in the list";

                   cout<<"\n4.Exit from the program";

                   do

                    {        cout<<"\nSelect your choice(1:4)";

                             cin>>c;

                             cout<<"";

                    }

                   while((c<1)||(c>4));

          if(c==4)exit(1);

          clrscr();

          switch(c)

{ case 1 :

          clrscr();

                   cout<<"How many elements : ";

                   cin>>n;

                   for(i=0;i<n;i++)

                   {        cout<<"Enter a number " <<i+1<< " : ";

                             cin>>element;

                             interpolation.add(element);

                   }

                   break;

          case 2 :

          clrscr();

                   interpolation.sort();

                   interpolation.display();

                   break;

          case 3 :

                   clrscr();

                   interpolation.sort();

                   cout<<"Enter the number to search : ";

                   cin>>element;

                   i= interpolation.search(element);

                   if(i==-1)

                             cout<<"Number is not present in the array ";

                   else

cout<<"The element " <<element<<" is at position "<<i+1<<" in the list ";

                   break;

          }

          cout<<"\nPress any key to continue............";

          getch();

      }

}