fork download
copy 
  1. //Sam Trivikraman                CS1A         	       	 Chapter 8, p. 488, #8
  2. //
  3. /*
  4.  ******************************************************************************
  5. Find Given Values
  6. _______________________________________________________________________________
  7. This program searches through a sorted array and finds the given value. 
  8. _______________________________________________________________________________
  9. INPUT
  10. the user's desired number				 : The number that the program searches for (user input)
  11.  
  12. OUTPUT
  13. count							 : The number of times the linear/binary search iterates 
  14. _______________________________________________________________________________
  15. *******************************************************************************
  16. */
  17. //
  18. #include <iostream>
  19. using namespace std;
  20.  
  21. //implement a linear search to find the given value
  22. int linSearch(int arr[], int num, int SIZE) {
  23.  
  24. 	int count;			//OUTPUT keeps track of the number of times the linear search iterates through the array
  25.  
  26. 	count = 0;
  27.  
  28. 	//search for the value in the array
  29. 	for(int i = 0; i < SIZE; i++)
  30. 	{
  31. 		if(num != arr[i])
  32. 		{
  33. 			count++;
  34. 		}
  35. 		else
  36. 		{
  37. 			return count;	
  38. 		}
  39. 	}
  40. 	//Output the number of times the search iterated through the array
  41. 	return count;
  42. }
  43.  
  44. //implement a binary search to find the given value
  45. int binSearch(int arr[], int num, int SIZE) {
  46.  
  47. 	int firstPos = 0;		//The position of the first value in the array
  48. 	int lastPos = SIZE - 1;	//The position of the last value in the array
  49. 	int middlePos;			//The position of the middle value in the array
  50. 	int position = -1;		//The position of the wanted value in the array
  51. 	bool found = false;		//a boolean flag
  52. 	int count;			//OUTPUT keeps track of the number of times the binary search iterates through the array
  53.  
  54. 	//search for the value in the array
  55. 	while (!found && firstPos <= lastPos)
  56. 	{
  57. 		middlePos = (firstPos + lastPos) / 2;
  58. 		if(arr[middlePos] == num)
  59. 		{
  60. 			found = true;
  61. 			position = middlePos;
  62. 			count = 1;
  63. 		}
  64. 		else if(arr[middlePos] > num)
  65. 		{
  66. 			lastPos = middlePos - 1;
  67. 			count++;
  68. 		}
  69. 		else
  70. 		{
  71. 			firstPos = middlePos + 1;
  72. 			count++;
  73. 		}
  74. 		//Output the number of times the search iterated through the array
  75. 		return count; 
  76. 	}
  77. 	return 0;
  78. }
  79.  
  80. int main() {
  81.  
  82. //Data Dictionary
  83. 	int SIZE = 20;		//CONSTANT the size of the array
  84. 	//INPUT the given array
  85. 	int array[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  86. 	int num;			//the user inputted value that should be searched for
  87.  
  88. 	//Get the user inputted value
  89. 	cout << "Please write a number." << endl;
  90. 	cin >> num;
  91.  
  92. 	//Search for the value using a linear search
  93. 	cout << linSearch(array, num, SIZE) << endl;
  94. 	//Search for the value using a linear search
  95. 	cout <<binSearch(array, num, SIZE) << endl;
  96.  
  97.  
  98. 	return 0;
  99. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
12
stdout
copy 
Please write a number.
11
1
https://ideone.com/B5ROvg
language:
C++ (gcc 8.3)
created:
18 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!