fork download
copy 
  1. //Nathan Dominguez                CSC5                      Chapter 8, P.487, #4
  2. //
  3. /*******************************************************************************
  4. *
  5. * Validate an Account Charge with a Binary Search
  6. *_______________________________________________________________________________
  7. * This program searches for a number with both binary and linear 
  8. * searches, and outputs how many searches it takes for each.
  9. *_______________________________________________________________________________
  10. *	INPUTS:
  11. *	  win		: the number to search for, input by the user.
  12. *	  numbers	: The list of valid numbers.
  13. *	  index		: the content of the current number being checked.
  14. *	  found		: Whether the number has been found.
  15. *	  first		: Start of array.
  16. *	  middle	: Middle of array.
  17. *	  last		: end of array.
  18. *	  position	: The current index being checked.
  19. *	OUTPUT:
  20. *	  numbinarysearch	: Amount of binary searches.
  21. *	  numlinearsearch	: Amount of linear searches.
  22. *******************************************************************************/
  23. #include <iostream>
  24. using namespace std;
  25.  
  26. int main()
  27. { 
  28. 	//decalre variables
  29. 	int win;                 //the number
  30. 	bool found = false;      //loosing numbers
  31. 	int first = 0;           //beginning of array
  32. 	int index;               //content of the current number being checked
  33. 	int middle;              //middle of array
  34. 	int last = 9;            //end of array
  35. 	int numlinearsearch=0;   //amount of linear searches
  36. 	int numbinarysearch=0;   //amount of binary searches
  37. 	int position = -1;       //check index
  38. 	int numbers[10] = {1357, 2671, 2672, 3345, 5555,
  39. 		    		   6243, 7777, 7922, 8547, 9121};
  40.  
  41. 	//INPUT number
  42. 	cout << "Enter the number to search for: " << endl;
  43. 	cin >> win;
  44.  
  45. 	//LINEAR SEARCH
  46. 	while (index < 10 && !found)
  47. 	{
  48. 		if (win == numbers[index])
  49. 		{
  50. 			found = true;
  51. 			position = index;
  52. 		}
  53. 		index++;
  54. 		numlinearsearch++;
  55. 	}
  56. 	found = false;
  57. 	position = -1;
  58. 	//
  59. 	//Binary search
  60. 	//LOOP - sort numbers and put them in order
  61. 	while (first < last && !found)
  62. 	{
  63. 		middle = (first+last)/2;   //calc middle
  64.  
  65. 		if(numbers[middle] == win) //success
  66. 		{
  67. 		found = true;
  68. 		position = middle;
  69. 		}
  70. 		else if (numbers[middle] > win)  //too low
  71. 		last = middle - 1;
  72.  
  73. 		else    //too high
  74. 		last = middle + 1;
  75. 		numbinarysearch++;
  76. 	}
  77. 	cout << "Linear search found the number in " << numlinearsearch; 
  78. 	cout << " searches." << endl;
  79. 	cout << "Binary search found the number in " << numbinarysearch; 
  80. 	cout << " searches.";
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter the number to search for: 
Linear search found the number in 10 searches.
Binary search found the number in 2 searches.
https://ideone.com/FRIb3Q
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

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!