Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.     int len1, len2;
  8.     scanf("%d %d", &len1, &len2);  
  9.  
  10.     int vetor_a[len1], vetor_b[len2];
  11.  
  12.     for (int i = 0; i < len1; i++) {
  13.         scanf("%d", &vetor_a[i]);
  14.     }
  15.     for (int i = 0; i < len2; i++) {
  16.         scanf("%d", &vetor_b[i]);
  17.     }
  18.  
  19.     // binary search
  20.     sort(&vetor_a[0], &vetor_a[len1]);
  21.  
  22.     int ini, fim;
  23.     int meio, key = 0;
  24.    
  25.     while (key < len2) {
  26.         ini = 0;
  27.         fim = len1 - 1;
  28.        
  29.         while (ini <= fim) {
  30.             meio = (fim + ini) / 2;
  31.            
  32.             printf("\n%d %d %d\n", fim, ini, meio);
  33.            
  34.             if (vetor_a[meio] > vetor_b[key]) {
  35.                 fim = meio - 1;
  36.             } else if (vetor_a[meio] < vetor_b[key]) {
  37.                 ini = meio + 1;
  38.             } else {    // vetor_a[meio] == vetor_b[key]
  39.                 break;
  40.             }
  41.         }
  42.  
  43.         while (meio + 1 < len1 && vetor_a[meio] == vetor_a[meio + 1]) meio++;
  44.  
  45.         printf("cont: %d ", meio + 1);
  46.         key++;
  47.     }
  48.     printf("\n");
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement