allia

классический бинарный поиск

Sep 18th, 2020
1,549
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.   int n = 0, m = 0, left = 0, right = 0, t = 0;
  9.  
  10.   cin >> n;
  11.   int arr[n];
  12.   for (int i = 0; i<n; i++)
  13.   cin >> arr[i];
  14.  
  15.   right = n-1;
  16.  
  17.   cin >> m;
  18.   int ar[m];
  19.   for (int i = 0; i<m; i++)
  20.    {
  21.      cin >> ar[i];
  22.      if (ar[i]<arr[0] || ar[i]>arr[n-1])
  23.      ar[i] = -1;
  24.      else while (left<=right)
  25.       {
  26.         int mid = (left+right)/2;
  27.         if (ar[i] == arr[mid])
  28.         {
  29.           ar[i] = mid+1;
  30.           t++;
  31.           break;
  32.         }
  33.         if (ar[i]<arr[mid])
  34.         right = mid-1;
  35.         else left = mid+1;
  36.       }
  37.       if (t == 0)
  38.       ar[i] = -1;
  39.       t = 0;
  40.       left = 0;
  41.       right = n-1;
  42.     }
  43.    for (int i = 0; i<m; i++)
  44.    cout << ar[i] << endl;
  45. }
RAW Paste Data