Advertisement
35657

Untitled

Apr 3rd, 2024
586
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1.  
  2. using namespace std;
  3.  
  4. #include <iostream>
  5. #include <vector>
  6.  
  7.  
  8. int binarySearch(std::vector<int>& arr, int x, int left, int right) {
  9.     if (right <= left) {
  10.         // промежуток пуст
  11.         return -1;
  12.     }
  13.     // промежуток не пуст
  14.     int mid = (left + right) / 2;
  15.     if (arr[mid] == x) {
  16.         // центральный элемент — искомый
  17.         return mid;
  18.     }
  19.     else if (x < arr[mid]) {
  20.         // искомый элемент меньше центрального значит следует искать в левой половине
  21.         return binarySearch(arr, x, left, mid);
  22.     }
  23.     else {
  24.         // иначе следует искать в правой половине
  25.         return binarySearch(arr, x, mid + 1, right);
  26.     }
  27. }
  28.  
  29. int binarySearch2(std::vector<int>& arr, int x, int left, int right) {
  30.     if (right <= left) {
  31.         // промежуток пуст
  32.         return -1;
  33.     }
  34.     // промежуток не пуст
  35.     int mid = (left + right) / 2;
  36.     if (arr[mid] == x) {
  37.         // центральный элемент — искомый
  38.         return mid;
  39.     }
  40.     return  x < arr[mid] ? binarySearch2(arr, x, left, mid) : binarySearch2(arr, x, mid + 1, right);
  41. }
  42.  
  43. int binarySearch3(std::vector<int>& arr, int x, int left, int right) {
  44.     if (right <= left) {
  45.         // промежуток пуст
  46.         return -1;
  47.     }
  48.     // промежуток не пуст
  49.     int mid = (left + right) / 2;
  50.     if (arr[mid] == x) {
  51.         // центральный элемент — искомый
  52.         return mid;
  53.     }
  54.     if (x < arr[mid]) {
  55.         // искомый элемент меньше центрального значит следует искать в левой половине
  56.         return binarySearch3(arr, x, left, mid);
  57.     }
  58.     if (x > arr[mid]) {
  59.         // иначе следует искать в правой половине
  60.         return binarySearch3(arr, x, mid + 1, right);
  61.     }
  62. }
  63.  
  64. int main() {
  65.     vector<int> arr(1000000);
  66.    
  67.     for (int i = 0; i < 1000000; i++) {
  68.         arr[i] = i;
  69.     }
  70.  
  71.     int index, x = 999999;
  72.  
  73.     int start_time = clock();
  74.  
  75.     for (int i = 0; i < 1000000; i++) {
  76.         index = binarySearch(arr, x, 0, arr.size());
  77.     }
  78.    
  79.     int end_time = clock();
  80.  
  81.     cout << "index " << index << ", time " << end_time - start_time << " milliseconds" << endl;
  82.  
  83.     start_time = clock();
  84.  
  85.     for (int i = 0; i < 1000000; i++) {
  86.         index = binarySearch2(arr, x, 0, arr.size());
  87.     }
  88.  
  89.     end_time = clock();
  90.  
  91.     cout << "index " << index << ", time " << end_time - start_time << " milliseconds" << endl;
  92.  
  93.     start_time = clock();
  94.  
  95.     for (int i = 0; i < 1000000; i++) {
  96.         index = binarySearch3(arr, x, 0, arr.size());
  97.     }
  98.  
  99.     end_time = clock();
  100.  
  101.     cout << "index " << index << ", time " << end_time - start_time << " milliseconds" << endl;
  102. }
  103.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement