Advertisement
corneliaprim

linear/binary sort

Apr 21st, 2019
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.51 KB | None | 0 0
  1.  
  2.  
  3. // Headers
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <string>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. //prototypes
  12. int linearSearch (int values[], int, int );
  13.  
  14. int binarySearch (int values[], int, int);
  15.  
  16. int main()
  17. {
  18.     int value;
  19.     int linearResult;
  20.     int binaryResult;
  21.  
  22. ///////////////////////////////////////////////////////////////////////
  23.     //input values into the array
  24.     int values[20]={101, 142, 147, 189, 199, 207, 222, 234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600};
  25. ///////////////////////////////////////////////////////////////////////
  26.     //ask for input
  27.     cout << "What value are you searching for? " << endl;
  28.     cin >> value;
  29. ///////////////////////////////////////////////////////////////////////
  30.     //call linear search
  31.      linearResult = linearSearch(values, 20, value);
  32. ///////////////////////////////////////////////////////////////////////
  33.      binaryResult = binarySearch(values, 20, binaryValue);
  34. ///////////////////////////////////////////////////////////////////////
  35. //test the results
  36.     if(linearResult >=0)
  37.     {
  38.         cout << "The number " << values << " was found in index " << linearResult << endl;
  39.         cout << "It took the linear search algorithm" << linearResult << " comparisons." << endl;
  40.         cout << "It took the binary search algorithm " << binaryResult << " comparisons." << endl;
  41.     }
  42.     else
  43.     {
  44.         cout << "The number " << value << " was not found" << endl;
  45.     }
  46. /////////////////////////////////////////////////////////////////////
  47.  
  48. return 0;
  49. }
  50. //Sort the array of values the long way
  51. int linearSearch (int values[], int size, int searchValue)
  52. {
  53.    for(int i=0; i<size; i++) //loop through the values
  54.    {
  55.      if (searchValue == values[i]) //if the value is found then return the value
  56.      {return i;}
  57.    }
  58.    return -1; //if did not find the search value
  59.  
  60. }
  61. //Binary search function
  62. int binarySearch (int values[], int size, int binaryValue)
  63. {
  64.     bool found =false;
  65.  
  66.    int first=0, //first element in the array
  67.         last = size-1, //next to last element
  68.         middle,
  69.         position = -1;
  70.  
  71.         while (!!found && first <= last)
  72.         middle=(first+last)/2;
  73.         if (values[middle] == binaryValue)
  74.             {found =true;
  75.             position = middle;
  76.             }
  77.         else if (values[middle] > binaryValue)
  78.         last = middle - 1;
  79.         else
  80.             first=middle+1;
  81.         if (position == -1)
  82.             binaryValue++;
  83.  
  84. return position;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement