fork download
copy 
  1. //Natalie Zarate                   CSC 5                   Chapter 8, P. 487, #8
  2. /*******************************************************************************
  3.  * DISPLAY TOTAL COMPARISONS
  4.  * 
  5.  * This program will accept a value between the 3rd value of the Fibbonacci 
  6.  * sequence to the 23rd value as input, then, it will search for that value 
  7.  * and display how many times it had to compare values using two different 
  8.  * methods of searching,
  9.  * _____________________________________________________________________________
  10.  * INPUT 
  11.  * 
  12.  * integers                                  - number of elements in 
  13.  *                                             pre-intialized array
  14.  * array[integers]                           - 3rd to 23rd value of Fibbonacci 
  15.  *                                             sequence. 
  16.  * searchNum                                 - inputted value program will 
  17.  *                                             search for
  18.  * lcomparisons                              - number of comparisons made using 
  19.  *                                             linear search
  20.  * bcomparisons                              - number of comparisons made using
  21.  *                                             binary search
  22.  * LinearSearch(array, integers, searchNum)  - function; searches for value
  23.  *                                             using linear search
  24.  * BinarySearch(array, integers, searchNum)  - function; searches for value 
  25.  *                                             using binary search
  26.  * 
  27.  * OUTPUT
  28.  * 
  29.  * DisplayResult(lcomparisons, bcomparisons) - functuon; outputs total number of 
  30.  *                                             comparisons needed to find value
  31.  *                                             for linear and binary search.
  32.  ******************************************************************************/ 
  33. #include <iostream>
  34. using namespace std;
  35.  
  36. // Prototype for LinearSearch
  37. int LinearSearch(int numbers[], int size, int search);
  38.  
  39. //Prototype for BinarySearch
  40. int BinarySearch(int numbers[], int size, int search);
  41.  
  42. //Prototype 
  43. void DisplayResult(int linear, int binary);
  44.  
  45. int main() 
  46. {
  47. 	/********************************************************************
  48. 	 * CONSTANTS
  49. 	 * ------------------------------------------------------------------
  50. 	 * integers - size of array holding fibonacci sequence
  51. 	 * array[integers] - 3 to 23rd values of fibonacci sequence
  52. 	 *******************************************************************/ 
  53. 	int integers = 20;  
  54. 	int array[integers] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 
  55. 	                      377, 590, 967, 1557, 2524, 4081, 6605, 10686};
  56.  
  57. 	int searchNum;    // INPUT - user-inputted value
  58.     int	lcomparisons; // INPUT - number of comparisons when using linear search
  59.     int bcomparisons; // INPUT - number of comparisons when using binary search
  60.  
  61. 	// Prompt for number to look for
  62. 	cout << "Enter a positive integer: " << endl;
  63. 	cin >> searchNum;
  64.  
  65. 	// Call LinearSearch
  66. 	lcomparisons = LinearSearch(array, integers, searchNum);
  67.  
  68. 	//Call BinarySort
  69. 	bcomparisons = BinarySearch(array, integers, searchNum);
  70.  
  71. 	//Call DisplayResult
  72. 	DisplayResult (lcomparisons, bcomparisons);
  73.  
  74. 	return 0;
  75. }
  76.  
  77. /*******************************************************************************
  78.  * FUNCTION LINEAR SEARCH
  79.  * 
  80.  * This function will search for the user-inputted value using linear searching,
  81.  * then return the number of comparisons it needed before finding the value. 
  82.  * 
  83.  *______________________________________________________________________________
  84.  * INPUT
  85.  * 
  86.  * subscript - element being searched
  87.  * element - location of user-inputted value
  88.  * found - flag; indicates if the value was found
  89.  * 
  90.  * OUTPUT
  91.  * sortcount - counter for number of times values were compared
  92.  ******************************************************************************/
  93.  int LinearSearch (int numbers[], int size, int search)
  94.  {
  95. 	/********************************************************************
  96. 	 * CONSTANTS
  97. 	 * ------------------------------------------------------------------
  98. 	 * subscript - element being searched
  99. 	 *******************************************************************/
  100.  
  101.  	int subscript = 0;
  102.  
  103.  	int element = -1;   // INPUT - location of user-inputted value
  104.  	bool found = false; // INPUT - flag; indicates if the value was found
  105.  	int sortcount = 0;  // OUTPUT - counter for number of times values were 
  106.  	                    //          compared
  107.  
  108.  	// step through array
  109.  	while (subscript < size && !found)
  110.  	{
  111.  		//If value is found
  112.  		if (numbers[subscript] == search)
  113.  		{
  114.  			found = true;
  115.  
  116.  			//Record value's subscript 
  117.  			element = subscript;
  118.  
  119.  		}
  120.  
  121.  		//Record comparison
  122.  		sortcount++;
  123.  
  124.  		//move on to next subscript
  125.  		subscript++;
  126.  	}
  127.  
  128.  	return sortcount;
  129.  }
  130. /*******************************************************************************
  131.  * FUNCTION  BINARYSEARCH
  132.  * 
  133.  * This program will find the user-inputted value using binary searching, then 
  134.  * return the number of comparisons it needed before finding the value. 
  135.  * _____________________________________________________________________________
  136.  * INPUT
  137.  * 
  138.  * firstElem - first element in array
  139.  * middle    - reference point; midpoint in chunk of array
  140.  * lastELem  - last element in array
  141.  * element   - location of user-inputted value
  142.  * found     - flag; indicates if the value was found
  143.  * 
  144.  * OUTPUT
  145.  * 
  146.  * sortcount - number of comparisons before value was found
  147.  ******************************************************************************/ 
  148. int BinarySearch(int numbers[], int size, int search)
  149. {
  150.  
  151. 	int firstElem = 0;       // INPUT - first element in array
  152. 	int middle;              // INPUT - reference point; midpoint in chunk of 
  153. 	                         //         array
  154. 	int lastElem = size - 1; // INPUT - last element in array
  155. 	int element = - 1;       // INPUT - location of user-inputted value
  156. 	bool found = false;      // INPUT - flag; indicates if the value was found
  157. 	int sortcount = 0;       // OUTPUT - number of comparisons before value was 
  158. 	                         //          found 
  159.  
  160. 	// step through array
  161. 	while(!found && firstElem <= lastElem)
  162. 	{
  163. 		middle = (firstElem + lastElem) / 2;
  164.  
  165. 		// if the user-input is equal to the middle-most value 
  166. 		if (numbers[middle] == search)
  167. 		{
  168. 			found = true;
  169. 			element = middle;
  170.  
  171. 			//increment comparison counter
  172. 			sortcount++;
  173. 		}
  174.  
  175. 		// if user input is greter than middle-most value
  176. 		else if (numbers[middle] > middle)
  177. 		{
  178. 			//update middle
  179. 			lastElem = middle - 1;
  180.  
  181. 			// increment comparison counter
  182. 			sortcount++;
  183. 		}
  184.  
  185. 		// if user input is less than middle-most value
  186. 		else
  187. 		{
  188. 			// update middle
  189. 			firstElem = middle + 1;
  190.  
  191. 			// increment comparison counter
  192. 			sortcount++;
  193. 		}
  194. 	}
  195.  
  196. 	return sortcount;
  197. }
  198. /*******************************************************************************
  199.  * FUNCTION DISPLAYRESULT
  200.  * 
  201.  * This function will display the total comparisons used in linear and binary 
  202.  * searches when searching for the user-inputted value.
  203.  * _____________________________________________________________________________
  204.  * OUTPUT
  205.  * 
  206.  * Message with total comparisons used in linear and binary search
  207.  ******************************************************************************/ 
  208. void DisplayResult(int linear, int binary)
  209. {
  210. 	cout << "Using Linear Sorting, it took " << linear << " comparisons to";
  211. 	cout << " find the value" << endl;
  212. 	cout << "Using Binary Sorting, it took " << binary << " comaprisons to";
  213. 	cout << " find the value";
  214.  
  215. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
10686
stdout
copy 
Enter a positive integer: 
Using Linear Sorting, it took 20 comparisons to find the value
Using Binary Sorting, it took 4 comaprisons to find the value
https://ideone.com/H3UWQl
CH 8 #8
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!