Advertisement
Guest User

Untitled

a guest
Nov 28th, 2015
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.84 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. bool is_between(int a, int b, int x) {
  6. if (a < b) {
  7. return (x >= a and x <= b);
  8. } else {
  9. return (x >= b and x <= a);
  10. }
  11. }
  12.  
  13. bool is_between2(int a, int b, int x) {
  14. return (x >= a and x <= b) or (x >= b and x <= a);
  15. }
  16.  
  17. int find(int *tab, int n, int x) {
  18. int l = 0;
  19. int r = n - 1;
  20. while (l <= r) {
  21. int m = (l + r) / 2;
  22. if (tab[m] == x) {
  23. return m + 1;
  24. }
  25. if (tab[l] < tab[r]) {
  26. if (tab[m] > tab[l]) {
  27. if (tab[m] < tab[r]) {
  28. if (x > tab[m] and x <= tab[r]) {
  29. l = m + 1;
  30. } else {
  31. r = m - 1;
  32. }
  33. } else {
  34. if (x >= tab[r] and x < tab[m]) {
  35. l = m + 1;
  36. } else {
  37. r = m - 1;
  38. }
  39. }
  40. } else {
  41. if (x > tab[m] and x <= tab[l]) {
  42. r = m - 1;
  43. } else {
  44. l = m + 1;
  45. }
  46. }
  47. } else {
  48. if (tab[m] < tab[l]) {
  49. if (tab[m] < tab[r]) {
  50. if (x > tab[m] and x <= tab[r]) {
  51. l = m + 1;
  52. } else {
  53. r = m - 1;
  54. }
  55. } else {
  56. if (x >= tab[r] and x < tab[m]) {
  57. l = m + 1;
  58. } else {
  59. r = m - 1;
  60. }
  61. }
  62. } else {
  63. if (x >= tab[l] and x < tab[m]) {
  64. r = m - 1;
  65. } else {
  66. l = m + 1;
  67. }
  68.  
  69. }
  70. }
  71. }
  72. return -1;
  73. }
  74.  
  75. int find2(int *tab, int n, int x) {
  76. int l = 0;
  77. int r = n - 1;
  78. while (l <= r) {
  79. int m = (l + r) / 2;
  80. if (tab[m] == x) {
  81. return m + 1;
  82. }
  83. if (tab[l] < tab[r]) {
  84. if (tab[m] > tab[l]) {
  85. if (is_between(tab[m], tab[r], x)) {
  86. l = m + 1;
  87. } else {
  88. r = m - 1;
  89. }
  90. } else {
  91. if (is_between(tab[m], tab[l], x)) {
  92. r = m - 1;
  93. } else {
  94. l = m + 1;
  95. }
  96. }
  97. } else {
  98. if (tab[m] < tab[l]) {
  99. if (is_between(tab[m], tab[r], x)) {
  100. l = m + 1;
  101. } else {
  102. r = m - 1;
  103. }
  104. } else {
  105. if (is_between(tab[m], tab[l], x)) {
  106. r = m - 1;
  107. } else {
  108. l = m + 1;
  109. }
  110. }
  111. }
  112. }
  113. return -1;
  114. }
  115.  
  116. int find3(int *tab, int n, int x) {
  117. int l = 0;
  118. int r = n - 1;
  119. while (l <= r) {
  120. int m = (l + r) / 2;
  121. if (tab[m] == x) {
  122. return m + 1;
  123. }
  124. if ((tab[l] < tab[r] and tab[l] < tab[m]) or (tab[l] > tab[r] and tab[l] > tab[m])) {
  125. if (is_between(tab[m], tab[r], x)) {
  126. l = m + 1;
  127. } else {
  128. r = m - 1;
  129. }
  130. } else {
  131. if (is_between(tab[m], tab[l], x)) {
  132. r = m - 1;
  133. } else {
  134. l = m + 1;
  135. }
  136. }
  137. }
  138. return -1;
  139. }
  140.  
  141. int main() {
  142. int n, k;
  143. cin >> n >> k;
  144. int tab[n];
  145. for (int i = 0; i < n; i++) {
  146. cin >> tab[i];
  147. }
  148. for (int i = 0; i < k; i++) {
  149. int x;
  150. cin >> x;
  151. cout << find(tab, n, x) << " ";
  152. }
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement