fork download
copy 
  1. // Chapter 3.1 of the book on page 195 contains the interative binary search algorithm.
  2. // Chapter 5.4 of the book on page 364 contains the recursive binary search algorithm, this is implement below.
  3.  
  4.  
  5. #include <iostream>
  6. using namespace std;
  7.  
  8. // function prototype
  9. int binarySearch(const int[], int, int, int);
  10. const int SIZE = 20;
  11.  
  12. int main()
  13. {
  14. 	int tests[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  15. 	int result;
  16. 	int searchFor;
  17.  
  18. 	cout << "Enter the number you wish to search for: ";
  19. 	cin >> searchFor;
  20. 	result = binarySearch(tests, 0, SIZE - 1, searchFor);
  21. 	if (result == -1)
  22. 		cout << "That number does not exist in the list.\n";
  23. 	else
  24. 	{
  25. 		cout << "That number is in the list. It is found at index " << result;
  26. 		cout << " in the array.\n";
  27. 	}
  28. 	return 0;
  29. }
  30.  
  31. int binarySearch(const int array[], int first, int last, int value) 
  32. {
  33. 	int midpoint;
  34. 	if (first > last)
  35. 		return -1;
  36. 	midpoint = (first + last)/2;
  37. 	if(array[midpoint]==value)
  38. 		return midpoint;
  39. 	if(array[midpoint] < value)
  40. 		return binarySearch(array, midpoint+1, last, value);
  41. 	else
  42. 		return binarySearch(array, first, midpoint-1, value);
  43. }
Success #stdin #stdout 0s 4172KB
comments (?)
stdin
copy 
22
stdout
copy 
Enter the number you wish to search for: That number does not exist in the list.
https://ideone.com/jWCPQV
language:
C++ (gcc 8.3)
created:
6 years 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!