Advertisement
Guest User

Untitled

a guest
Nov 16th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. int binary_search(vector<int> marble, int size, int key)
  9. {
  10.     int begin = 0;
  11.     int end = size;
  12.     int middle;
  13.     while (begin <= end) {
  14.         middle = (begin + end) / 2;
  15.         if (marble[middle] < key) {
  16.             begin = middle + 1;
  17.         } else if (marble[middle] > key) {
  18.             end = middle - 1;
  19.         } else {
  20.             return middle;
  21.         }
  22.     }
  23.     return -1;
  24. }
  25.  
  26. void testing(vector<int> marble, vector<int> tests, int n_of_tests, int n, int loop){
  27.     cout << "CASE# " << loop << ":" << endl;
  28.     for(int i = 0; i < n_of_tests; i++){
  29.         int aux = tests[i];
  30.         int flag = binary_search(marble,n,aux);
  31.         if(flag == -1){
  32.             cout << tests[i] << " not found" << endl;
  33.         } else {
  34.             cout << tests[i] << " found at " << flag << endl;
  35.         }
  36.     }
  37. }
  38. void reading(int loop){
  39.     vector<int> marble;
  40.     int n, n_of_tests, aux;
  41.     cin >> n >> n_of_tests;
  42.     if((n == 0) && (n_of_tests == 0)){
  43.         return;
  44.     }
  45.     for(int i = 0;i < n; i++){
  46.         cin >> aux;
  47.         marble.push_back(aux);
  48.     }
  49.     vector<int> tests;
  50.     for(int i = 0; i < n_of_tests; i++){
  51.         cin >> aux;
  52.         tests.push_back(aux);
  53.     }
  54.     std::sort(marble.begin(),marble.end());
  55.     // for(int i = 0; i < marble.size(); i++){
  56.     //  cout << marble[i] << endl;
  57.     // }
  58.     testing(marble,tests,n_of_tests,n,loop);
  59.     reading(loop+1);
  60. }
  61.  
  62. int main(){
  63.     reading(1);
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement