Advertisement
StoneHaos

2

Jan 23rd, 2022
55
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 QSort(int *arr, int n) {
  23. if (n == 1) return;
  24. int l = 0;
  25. int r = n - 1;
  26. int pivot = (l + r + 1) / 2;
  27. while (l < r) {
  28. while (l < pivot && arr[l] <= arr[pivot]) ++ l;
  29. while (r > pivot && arr[r] >= arr[pivot]) -- r;
  30. if (l >= r) continue;
  31. swap(arr[l], arr[r]);
  32. if (l == pivot) pivot = r;
  33. else if (r == pivot) pivot = l;
  34. }
  35. QSort(arr, pivot);
  36. QSort(arr + pivot, n - pivot);
  37. }
  38.  
  39. int BS(int *arr, int n, int e) {
  40. int l = 0;
  41. int r = n;
  42. while (r - l > 1) {
  43. int m = (r + l) / 2;
  44. if (e < arr[m])
  45. r = m;
  46. else
  47. l = m;
  48. }
  49. return ((e == arr[l]) ? l : -1);
  50. }
  51.  
  52. int main(void) {
  53. srand(time(NULL));
  54. int n;
  55. cin >> n;
  56. int *arr = (int*)malloc(n * sizeof(int));
  57. for (int i = 0; i < n; ++ i) {
  58. arr[i] = rand() % 100;
  59. }
  60. print(arr, n);
  61. cout << "> ";
  62. int a;
  63. cin >> a;
  64. cout << LS(arr, n, a) << endl << endl;
  65. QSort(arr, n);
  66. print(arr, n);
  67. cout << "> ";
  68. cin >> a;
  69. cout << BS(arr, n, a) << endl << endl;
  70. free(arr);
  71. return 0;
  72. }
Advertisement
RAW Paste Data Copied
Advertisement