// Marvyn Jesse De La Torre CS1A Chapter 8 #8 pg.488
//
/*************************************************************
* Search Benchmarks
*
* This program compares linear search and binary search
* by counting the number of comparisons required.
*
* Input:
* num: The number to search for
*
* Output:
* Displays the comparison count for each search method.
*************************************************************/
#include <iostream>
using namespace std;
int linearSearch( int arr[ ] , int size, int num, int & count) ;
int binarySearch( int arr[ ] , int size, int num, int & count) ;
int main( )
{
int arr[ ] = {
3 , 6 , 9 , 12 , 15 , 18 , 21 , 24 , 27 , 30 ,
33 , 36 , 39 , 42 , 45 , 48 , 51 , 54 , 57 , 60
} ;
int size = sizeof ( arr) / sizeof ( arr[ 0 ] ) ;
int num;
int linearCount = 0 ;
int binaryCount = 0 ;
cout << "Enter the number to search for: " ;
cin >> num;
int linearResult = linearSearch( arr, size, num, linearCount) ;
int binaryResult = binarySearch( arr, size, num, binaryCount) ;
if ( linearResult == - 1 )
{
cout << "Number was not found using linear search." << endl;
}
else
{
cout << "Linear search found the number." << endl;
}
cout << "Linear search comparisons: " << linearCount << endl;
if ( binaryResult == - 1 )
{
cout << "Number was not found using binary search." << endl;
}
else
{
cout << "Binary search found the number." << endl;
}
cout << "Binary search comparisons: " << binaryCount << endl;
return 0 ;
}
int linearSearch( int arr[ ] , int size, int num, int & count)
{
int position = - 1 ;
for ( int index = 0 ; index < size && position == - 1 ; index++ )
{
count++ ;
if ( arr[ index] == num)
{
position = index;
}
}
return position;
}
int binarySearch( int arr[ ] , int size, int num, int & count)
{
int first = 0 ;
int last = size - 1 ;
int position = - 1 ;
while ( position == - 1 && first <= last)
{
int middle = ( first + last) / 2 ;
count++ ;
if ( arr[ middle] == num)
{
position = middle;
}
else if ( arr[ middle] > num)
{
last = middle - 1 ;
}
else
{
first = middle + 1 ;
}
}
return position;
}
Ly8gTWFydnluIEplc3NlIERlIExhIFRvcnJlICAgICBDUzFBICAgICBDaGFwdGVyIDggIzggcGcuNDg4Ci8vCi8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiogU2VhcmNoIEJlbmNobWFya3MKKgoqIFRoaXMgcHJvZ3JhbSBjb21wYXJlcyBsaW5lYXIgc2VhcmNoIGFuZCBiaW5hcnkgc2VhcmNoCiogYnkgY291bnRpbmcgdGhlIG51bWJlciBvZiBjb21wYXJpc29ucyByZXF1aXJlZC4KKgoqIElucHV0OgoqICAgbnVtOiBUaGUgbnVtYmVyIHRvIHNlYXJjaCBmb3IKKgoqIE91dHB1dDoKKiAgIERpc3BsYXlzIHRoZSBjb21wYXJpc29uIGNvdW50IGZvciBlYWNoIHNlYXJjaCBtZXRob2QuCioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCgojaW5jbHVkZSA8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbGluZWFyU2VhcmNoKGludCBhcnJbXSwgaW50IHNpemUsIGludCBudW0sIGludCAmY291bnQpOwppbnQgYmluYXJ5U2VhcmNoKGludCBhcnJbXSwgaW50IHNpemUsIGludCBudW0sIGludCAmY291bnQpOwoKaW50IG1haW4oKQp7CiAgICBpbnQgYXJyW10gPSB7CiAgICAgICAgMywgNiwgOSwgMTIsIDE1LCAxOCwgMjEsIDI0LCAyNywgMzAsCiAgICAgICAgMzMsIDM2LCAzOSwgNDIsIDQ1LCA0OCwgNTEsIDU0LCA1NywgNjAKICAgIH07CgogICAgaW50IHNpemUgPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwogICAgaW50IG51bTsKICAgIGludCBsaW5lYXJDb3VudCA9IDA7CiAgICBpbnQgYmluYXJ5Q291bnQgPSAwOwoKICAgIGNvdXQgPDwgIkVudGVyIHRoZSBudW1iZXIgdG8gc2VhcmNoIGZvcjogIjsKICAgIGNpbiA+PiBudW07CgogICAgaW50IGxpbmVhclJlc3VsdCA9IGxpbmVhclNlYXJjaChhcnIsIHNpemUsIG51bSwgbGluZWFyQ291bnQpOwogICAgaW50IGJpbmFyeVJlc3VsdCA9IGJpbmFyeVNlYXJjaChhcnIsIHNpemUsIG51bSwgYmluYXJ5Q291bnQpOwoKICAgIGlmIChsaW5lYXJSZXN1bHQgPT0gLTEpCiAgICB7CiAgICAgICAgY291dCA8PCAiTnVtYmVyIHdhcyBub3QgZm91bmQgdXNpbmcgbGluZWFyIHNlYXJjaC4iIDw8IGVuZGw7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgY291dCA8PCAiTGluZWFyIHNlYXJjaCBmb3VuZCB0aGUgbnVtYmVyLiIgPDwgZW5kbDsKICAgIH0KCiAgICBjb3V0IDw8ICJMaW5lYXIgc2VhcmNoIGNvbXBhcmlzb25zOiAiIDw8IGxpbmVhckNvdW50IDw8IGVuZGw7CgogICAgaWYgKGJpbmFyeVJlc3VsdCA9PSAtMSkKICAgIHsKICAgICAgICBjb3V0IDw8ICJOdW1iZXIgd2FzIG5vdCBmb3VuZCB1c2luZyBiaW5hcnkgc2VhcmNoLiIgPDwgZW5kbDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBjb3V0IDw8ICJCaW5hcnkgc2VhcmNoIGZvdW5kIHRoZSBudW1iZXIuIiA8PCBlbmRsOwogICAgfQoKICAgIGNvdXQgPDwgIkJpbmFyeSBzZWFyY2ggY29tcGFyaXNvbnM6ICIgPDwgYmluYXJ5Q291bnQgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQoKaW50IGxpbmVhclNlYXJjaChpbnQgYXJyW10sIGludCBzaXplLCBpbnQgbnVtLCBpbnQgJmNvdW50KQp7CiAgICBpbnQgcG9zaXRpb24gPSAtMTsKCiAgICBmb3IgKGludCBpbmRleCA9IDA7IGluZGV4IDwgc2l6ZSAmJiBwb3NpdGlvbiA9PSAtMTsgaW5kZXgrKykKICAgIHsKICAgICAgICBjb3VudCsrOwoKICAgICAgICBpZiAoYXJyW2luZGV4XSA9PSBudW0pCiAgICAgICAgewogICAgICAgICAgICBwb3NpdGlvbiA9IGluZGV4OwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gcG9zaXRpb247Cn0KCmludCBiaW5hcnlTZWFyY2goaW50IGFycltdLCBpbnQgc2l6ZSwgaW50IG51bSwgaW50ICZjb3VudCkKewogICAgaW50IGZpcnN0ID0gMDsKICAgIGludCBsYXN0ID0gc2l6ZSAtIDE7CiAgICBpbnQgcG9zaXRpb24gPSAtMTsKCiAgICB3aGlsZSAocG9zaXRpb24gPT0gLTEgJiYgZmlyc3QgPD0gbGFzdCkKICAgIHsKICAgICAgICBpbnQgbWlkZGxlID0gKGZpcnN0ICsgbGFzdCkgLyAyOwoKICAgICAgICBjb3VudCsrOwoKICAgICAgICBpZiAoYXJyW21pZGRsZV0gPT0gbnVtKQogICAgICAgIHsKICAgICAgICAgICAgcG9zaXRpb24gPSBtaWRkbGU7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYgKGFyclttaWRkbGVdID4gbnVtKQogICAgICAgIHsKICAgICAgICAgICAgbGFzdCA9IG1pZGRsZSAtIDE7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGZpcnN0ID0gbWlkZGxlICsgMTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIHBvc2l0aW9uOwp9