Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- bool is_between(int a, int b, int x) {
- if (a < b) {
- return (x >= a and x <= b);
- } else {
- return (x >= b and x <= a);
- }
- }
- bool is_between2(int a, int b, int x) {
- return (x >= a and x <= b) or (x >= b and x <= a);
- }
- int find(int *tab, int n, int x) {
- int l = 0;
- int r = n - 1;
- while (l <= r) {
- int m = (l + r) / 2;
- if (tab[m] == x) {
- return m + 1;
- }
- if (tab[l] < tab[r]) {
- if (tab[m] > tab[l]) {
- if (tab[m] < tab[r]) {
- if (x > tab[m] and x <= tab[r]) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- } else {
- if (x >= tab[r] and x < tab[m]) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- } else {
- if (x > tab[m] and x <= tab[l]) {
- r = m - 1;
- } else {
- l = m + 1;
- }
- }
- } else {
- if (tab[m] < tab[l]) {
- if (tab[m] < tab[r]) {
- if (x > tab[m] and x <= tab[r]) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- } else {
- if (x >= tab[r] and x < tab[m]) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- }
- } else {
- if (x >= tab[l] and x < tab[m]) {
- r = m - 1;
- } else {
- l = m + 1;
- }
- }
- }
- }
- return -1;
- }
- int find2(int *tab, int n, int x) {
- int l = 0;
- int r = n - 1;
- while (l <= r) {
- int m = (l + r) / 2;
- if (tab[m] == x) {
- return m + 1;
- }
- if (tab[l] < tab[r]) {
- if (tab[m] > tab[l]) {
- if (is_between(tab[m], tab[r], x)) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- } else {
- if (is_between(tab[m], tab[l], x)) {
- r = m - 1;
- } else {
- l = m + 1;
- }
- }
- } else {
- if (tab[m] < tab[l]) {
- if (is_between(tab[m], tab[r], x)) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- } else {
- if (is_between(tab[m], tab[l], x)) {
- r = m - 1;
- } else {
- l = m + 1;
- }
- }
- }
- }
- return -1;
- }
- int find3(int *tab, int n, int x) {
- int l = 0;
- int r = n - 1;
- while (l <= r) {
- int m = (l + r) / 2;
- if (tab[m] == x) {
- return m + 1;
- }
- if ((tab[l] < tab[r] and tab[l] < tab[m]) or (tab[l] > tab[r] and tab[l] > tab[m])) {
- if (is_between(tab[m], tab[r], x)) {
- l = m + 1;
- } else {
- r = m - 1;
- }
- } else {
- if (is_between(tab[m], tab[l], x)) {
- r = m - 1;
- } else {
- l = m + 1;
- }
- }
- }
- return -1;
- }
- int main() {
- int n, k;
- cin >> n >> k;
- int tab[n];
- for (int i = 0; i < n; i++) {
- cin >> tab[i];
- }
- for (int i = 0; i < k; i++) {
- int x;
- cin >> x;
- cout << find(tab, n, x) << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement