Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Headers
- #include <iostream>
- #include <cstdlib>
- #include <string>
- #include <algorithm>
- using namespace std;
- //prototypes
- int linearSearch (int values[], int, int );
- int binarySearch (int values[], int, int);
- int main()
- {
- int value;
- int linearResult;
- int binaryResult;
- ///////////////////////////////////////////////////////////////////////
- //input values into the array
- int values[20]={101, 142, 147, 189, 199, 207, 222, 234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600};
- ///////////////////////////////////////////////////////////////////////
- //ask for input
- cout << "What value are you searching for? " << endl;
- cin >> value;
- ///////////////////////////////////////////////////////////////////////
- //call linear search
- linearResult = linearSearch(values, 20, value);
- ///////////////////////////////////////////////////////////////////////
- binaryResult = binarySearch(values, 20, binaryValue);
- ///////////////////////////////////////////////////////////////////////
- //test the results
- if(linearResult >=0)
- {
- cout << "The number " << values << " was found in index " << linearResult << endl;
- cout << "It took the linear search algorithm" << linearResult << " comparisons." << endl;
- cout << "It took the binary search algorithm " << binaryResult << " comparisons." << endl;
- }
- else
- {
- cout << "The number " << value << " was not found" << endl;
- }
- /////////////////////////////////////////////////////////////////////
- return 0;
- }
- //Sort the array of values the long way
- int linearSearch (int values[], int size, int searchValue)
- {
- for(int i=0; i<size; i++) //loop through the values
- {
- if (searchValue == values[i]) //if the value is found then return the value
- {return i;}
- }
- return -1; //if did not find the search value
- }
- //Binary search function
- int binarySearch (int values[], int size, int binaryValue)
- {
- bool found =false;
- int first=0, //first element in the array
- last = size-1, //next to last element
- middle,
- position = -1;
- while (!!found && first <= last)
- middle=(first+last)/2;
- if (values[middle] == binaryValue)
- {found =true;
- position = middle;
- }
- else if (values[middle] > binaryValue)
- last = middle - 1;
- else
- first=middle+1;
- if (position == -1)
- binaryValue++;
- return position;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement