Advertisement
janac

Binary search, recursive

Dec 14th, 2021
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. // Binary search, recursive.
  2.  
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. // Find a number in a list.
  7. int find_number(int number_list[], int number_to_find,
  8.     int range_start, int range_end)
  9. {
  10.     int index_of_found_number = 0;
  11.     int range_middle; // This is the current middle of the range.
  12.  
  13.     // If we have searched all the sections,
  14.     if (range_start > range_end) {
  15.  
  16.         index_of_found_number = -1; // The number is not on the list.
  17.  
  18.     }
  19.     // If there is more to search,
  20.     else {
  21.  
  22.         // Find the middle of the range.
  23.         range_middle = (range_start + range_end) / 2;
  24.  
  25.         // If the middle number is equal to the number we're looking for,
  26.         if (number_list[range_middle] == number_to_find) {
  27.  
  28.             // It was found in the middle.
  29.             index_of_found_number = range_middle;
  30.         }
  31.         // If the middle number is greater than the number we're looking for,
  32.         else if (number_list[range_middle] > number_to_find) {
  33.  
  34.             // Search the range before the middle number.
  35.             index_of_found_number = find_number(number_list, number_to_find,
  36.                 range_start, range_middle - 1);
  37.         }
  38.         // If the middle number is less than the number we're looking for,
  39.         else {
  40.  
  41.             // Search the range after the middle number.
  42.             index_of_found_number = find_number(number_list, number_to_find,
  43.                 range_middle + 1, range_end);
  44.         }
  45.     }
  46.  
  47.     return index_of_found_number;
  48. }
  49.  
  50. int main()
  51. {  
  52.     // List of numbers to search.
  53.     int numbers[] = {2, 4, 6, 7, 9, 10, 14, 15, 17, 19, 26, 29};
  54.  
  55.     // Calculate the number of elements in the array.
  56.     int num_elements = sizeof(numbers) / sizeof(int);
  57.     int input = 0; // The number to look for.
  58.     int index = 0; // Index of found number.
  59.  
  60.     cout << "What number would you like to find? ";
  61.     cin >> input; // Get the number we are searching for.
  62.     // Search for the number.
  63.     index = find_number(numbers, input, 0, num_elements - 1);
  64.  
  65.     // If if the number was not found.
  66.     if (index == -1) cout << "The number " << input
  67.         << " is not on the list.\n";
  68.  
  69.     // Otherwise, if the number was found, display the
  70.     // index where it was found
  71.     else cout << "The number " << input << " is located at index "
  72.         << index << '\n';
  73.  
  74.     // End the program.
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement