SHARE
TWEET

Untitled

a guest Mar 26th, 2020 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <clocale>
  3. #include <time.h>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. int main()
  9. {
  10.     setlocale(LC_ALL, "Russian");
  11.  
  12.     const int N = 32; // количество элементов массива arr
  13.  
  14.     int arr[N]; // объявление массива E с n элементов
  15.     int a, b; // интервалы [a; b]
  16.     int X, L, R, c;
  17.     int average;
  18.     const int iterSize = 10;
  19.  
  20.     srand(time(0)); // каждый новый запуск, разные значения
  21.  
  22.     // интервалы [a; b]
  23.     cout << "Введите a:" << endl;
  24.     cin >> a;
  25.     cout << "Введите b:" << endl;
  26.     cin >> b;
  27.     cout << "Поиск значения: "; cin >> X;
  28.     int sum = 0;
  29.     for (int iter = 0; iter < iterSize; iter++)
  30.     {
  31.  
  32.         for (int i = 0; i < N; i++) {
  33.             arr[i] = a + rand() % (b - a + 1); // числа, сгенерированные  на интервале [a; b]
  34.         }
  35.  
  36.  
  37.         // Bubble sort
  38.         int temp;
  39.         for (int i = 0; i < N - 1; i++) {
  40.             for (int j = N - 2; j >= i; j--) {
  41.                 if (arr[j] > arr[j + 1]) {
  42.                     // меняем элементы местами
  43.                     temp = arr[j];
  44.                     arr[j] = arr[j + 1];
  45.                     arr[j + 1] = temp;
  46.                 }
  47.             }
  48.         }
  49.  
  50.         // Выводим отсортированный массив
  51.         cout << "[Array #" << iter + 1 << "]: ";
  52.         for (int i = 0; i < N; i++)
  53.         {
  54.             cout << arr[i] << " | ";
  55.         }
  56.  
  57.         int steps = 0;
  58.  
  59.         L = 0;
  60.         R = N;
  61.         while (L < R - 1)
  62.         {
  63.             steps += 1;
  64.  
  65.             c = (L + R) / 2;
  66.             if (X < arr[c])
  67.                 R = c;
  68.             else if (X == arr[c])
  69.                 break;
  70.             else
  71.                 L = c;
  72.         }
  73.  
  74.  
  75.         std::cout << "Steps: " << steps << std::endl;
  76.  
  77.         sum += steps;
  78.         //if (arr[L] == X)
  79.         //{
  80.         //    // cout << "A [" << L << "] =" << X << endl;
  81.         //}
  82.         //else
  83.         //    cout << "Не нашли!" << endl;
  84.     }
  85.  
  86.     average = sum / iterSize;
  87.     std::cout << "Сумма = " << sum << std::endl;
  88.     cout << "Среднее кол-во шагов при бинарном поиске для массива с " << N << " элементов в диапазоне 0 ... 100: " << average << endl;
  89.  
  90.     return 0;
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top