ptrawt

259201 Lab13.3

Nov 13th, 2014
266
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "iostream"
  2. #include "cstdlib"
  3. #include "ctime"
  4. using namespace std;
  5.  
  6. void binarySearch(int a[],int arraySize,int key);   //function prototype
  7.  
  8. int main()
  9. {
  10.     const int arraySize = 10;
  11.     int a[arraySize];
  12.     int key,index,to_do = arraySize - 1;
  13.     bool did_swap = true;
  14.  
  15.     srand(time(NULL));
  16.     for (int i = 0; i <= arraySize; i++)
  17.     {
  18.         a[i] = rand() % 100 + 1;    //generating random number between 1 - 100
  19.     }
  20.  
  21.     while( to_do >= 0 && did_swap)
  22.     {
  23.         index = 0;
  24.         did_swap = false;
  25.         while ( index <= to_do )
  26.         {
  27.             if (a[index] > a[index+1])
  28.             {
  29.                 int temp = a[index];
  30.                 a[index] = a[index+1];
  31.                 a[index+1] = temp;
  32.                 did_swap = true;
  33.             }
  34.             index = index+1;
  35.         }
  36.         cout << "to_do=" << to_do <<": ";
  37.         for (int i = 0; i <= arraySize; ++i)
  38.         {
  39.             cout<<a[i]<<" ";
  40.         }
  41.         cout << endl;
  42.         to_do = to_do-1;
  43.     }
  44.  
  45.  
  46.     cout <<"Enter search key: ";
  47.     cin >> key;
  48.     binarySearch(a,arraySize,key);
  49.  
  50.     return 0;
  51. }
  52.  
  53. void binarySearch(int a[],int arraySize,int key)
  54. {
  55.     bool found = false;
  56.     int low = 0,middle,high = (arraySize - 1),counter = 1;
  57.     while(low <= high)
  58.     {
  59.         cout<<"Pass#"<<counter<<": ";
  60.         for (int i = 0; i < arraySize; ++i)
  61.         {
  62.             if(i == low && low != high)
  63.             {
  64.                 cout<<"["<<a[i];
  65.             }
  66.             else if (i == high && low != high)
  67.             {
  68.                 cout<<" "<<a[i]<<"]";
  69.             }
  70.             else if (i == low && low == high)
  71.             {
  72.                 cout<<"["<<a[i]<<"]";
  73.             }
  74.             else
  75.             {
  76.                 cout<<" "<<a[i];
  77.             }
  78.         }
  79.  
  80.         middle = (low+high)/2;
  81.  
  82.         if(key == a[middle])
  83.         {
  84.             found = true;
  85.             cout <<endl<<"Found element "<<key<<" at index "<<middle<<endl;
  86.             break;
  87.         }
  88.         else if (key < a[middle])
  89.         {
  90.             high = middle - 1;          // search low end of array
  91.         }
  92.         else
  93.         {
  94.             low = middle + 1;           // search high end of array
  95.         }
  96.  
  97.         counter++;
  98.         cout<<endl;
  99.     }
  100.  
  101.     if(!found)
  102.     {
  103.         cout <<"Could not find element "<<key<<" in array a"<<endl;
  104.  
  105.     }
  106.  
  107. }
RAW Paste Data