fork download
copy 
  1. //Sam Trivikraman                CS1A         	       	 Chapter 8, p. 487, #3
  2. //
  3. /*
  4.  ******************************************************************************
  5. Find Winning Lottery Ticket Numbers (Modification)
  6. _______________________________________________________________________________
  7. This program finds whether or not the provided lottery tiocket number is a valid
  8. number in that week's set of tickets. 
  9. _______________________________________________________________________________
  10. INPUT
  11. the user's ticket						 : The ticket number that the program is seraching for (user input)
  12.  
  13. OUTPUT
  14. valid/invalid							 : Whether or not the number that is inputted is in the array
  15. _______________________________________________________________________________
  16. *******************************************************************************
  17. */
  18. //
  19.  
  20. #include <iostream>
  21. using namespace std;
  22.  
  23. //The function which contains a binary search 
  24. 	int binSearch(int arr[], int num, int SIZE)
  25. 	{
  26.  
  27. 	//Data Dictionary
  28. 	int firstPos = 0;			// The position of the first slot in the array		
  29. 	int lastPos = SIZE - 1;		// The position of the last slot in the array
  30. 	int middlePos;				// The position of the middle slot in the array
  31. 	int position = -1;			// A temporary variable of the position
  32. 	bool found = false;			//Used to see if the value was found in the array
  33.  
  34. 	//Implement the binary search to find the value the user inputted
  35. 	while (!found && firstPos <= lastPos)
  36. 	{
  37. 		middlePos = (firstPos + lastPos) / 2;
  38. 		if(arr[middlePos] == num)
  39. 		{
  40. 			found = true;
  41. 			position = middlePos;
  42. 		}
  43. 		else if(arr[middlePos] > num)
  44. 		{
  45. 			lastPos = middlePos - 1;
  46. 		}
  47. 		else
  48. 		{
  49. 			firstPos = middlePos + 1;
  50. 		}
  51.  
  52. 		//return the position where the ticket number was found
  53. 		return position; 
  54. 	}
  55. 	return 0;
  56. }
  57.  
  58.  
  59. int main() {
  60. //Data Dictionary
  61. 	int userTicketNum;			//INPUT the user's ticket number
  62. 	int SIZE = 10;				//CONSTANT the size of the array
  63. 	//INPUT the array with ticket values
  64. 	int tickets[SIZE] = {13579, 26791, 26792, 33445, 55555, 62483, 77777, 79422, 85647,93121};
  65. 	int results;				//INPUT contains the final results from the binary search
  66.  
  67. 	//Get inout from user (the user's ticket number)
  68. 	cout << "Please enter your ticket number." << endl;
  69. 	cin >> userTicketNum;
  70. 	//Check and output whether or not the ticket number is valid
  71. 	results = binSearch(tickets, userTicketNum, SIZE);
  72. 	if(results == -1)
  73. 	{
  74. 		cout << "This ticket number is invalid" << endl;
  75. 	}
  76. 	else
  77. 	{
  78. 		cout << "This ticket number is valid" << endl;
  79. 	}
  80.  
  81. 	return 0;	
  82. 	}
  83.  
  84.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
2
stdout
copy 
Please enter your ticket number.
This ticket number is invalid
https://ideone.com/khxe4W
language:
C++ (gcc 8.3)
created:
17 days 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!