Advertisement
StoneHaos

2

Feb 18th, 2022
558
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. void print(int *arr, int n) {
  9.     for (int i = 0; i < n; ++ i)
  10.         cout << arr[i] << " ";
  11.     cout << endl;
  12. }
  13.  
  14. int LS(int *arr, int n, int e) {
  15.     int res = -1;
  16.     for (int i = 0; i < n; ++ i) {
  17.         if (arr[i] == e) res = i;
  18.     }
  19.     return res;
  20. }
  21.  
  22. void Shell(int *a, int n, int d = 5) {
  23.     for (int t = ((d % 2 == 0) ? d + 1 : d); t > 0; t -= 2) {
  24.         for (int i = 1; i < n; i += t) {
  25.             for (int j = i; j - t >= 0 && a[j] < a[j - t]; j -= t)
  26.                 swap(a[j], a[j - t]);
  27.         }
  28.     }
  29. }
  30.  
  31. int IS(int *A, int N, int key) {
  32.     int m, l = 0, r = N - 1;
  33.     while (A[l] <= key && A[r] >= key) {
  34.         m = l + ((key - A[l])*(r - l)) / (A[r] - A[l]);
  35.         if (A[m] < key) l = m + 1;
  36.         else if (A[m] > key) r = m - 1;
  37.         else {
  38.             l = m;
  39.             break;
  40.         }
  41.     }
  42.     if (A[l] == key) return l; else return -1;
  43.  
  44. }
  45.  
  46. int main(void) {
  47.     srand(time(NULL));
  48.     int n;
  49.     cin >> n;
  50.     int *arr = (int*)malloc(n * sizeof(int));
  51.     for (int i = 0; i < n; ++ i) {
  52.         arr[i] = rand() % 100;
  53.     }
  54.     print(arr, n);
  55.     cout << "> ";
  56.     int a;
  57.     cin >> a;
  58.     cout << LS(arr, n, a) << endl << endl;
  59.     Shell(arr, n);
  60.     print(arr, n);
  61.     cout << "> ";
  62.     cin >> a;
  63.     cout << IS(arr, n, a) << endl << endl;
  64.     free(arr);
  65.     return 0;
  66. }
Advertisement
RAW Paste Data Copied
Advertisement