StoneHaos

7

Nov 28th, 2021
890
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int interpolatingSearch (int a[], int n, int key) {
  9.     //изначально устанавливаем нижний индекс на начало массива,
  10.     //а верний на конец массива
  11.     int lo = 0;
  12.     int hi = n - 1;
  13.     int mid = -1;
  14.     int index = -1;
  15.     while(lo <= hi) {
  16.         mid = lo + (((double)(hi - lo) / (a[hi] - a[lo])) * (key - a[lo]));
  17.         if(a[mid] == key) {index = mid; break;}
  18.         else {
  19.             if(a[mid] < key) {
  20.                 // если значение в ячейке с индексом mid меньше, то смещаем нижнюю границу
  21.                 lo = mid + 1;
  22.             } else {
  23.                 //в случае, если значение больше, то смещаем верхнюю границу
  24.                 hi = mid - 1;
  25.             }
  26.         }
  27.     }
  28.     return index;
  29. }
  30.  
  31. int main() {
  32.     srand(time(NULL));
  33.     int n;
  34.     cin >> n;
  35.     int *a = new int[n];
  36.     for (int i = 0; i < n; i++) a[i] = rand() % 50;
  37.     sort(a, a + n);
  38.     for (int i = 0; i < n; i++) cout << a[i] << " ";
  39.     cout << endl;
  40.     int key;
  41.     cin >> key;
  42.     cout << "index " << interpolatingSearch(a, n, key) << endl;
  43.     delete [] a;
  44.     return 0;
  45. }
RAW Paste Data