akela43

search2

Jun 8th, 2018
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <iostream>
  4. #include <vector>
  5.  
  6. int get_pos(const std::vector<long> &numbers, long number) {
  7.   // TODO optimize this function
  8.   long l = 0;
  9.   long r = numbers.size() - 1;
  10.   while (l <= r) {
  11.     long m = l + ( (r - l) / 2);
  12.     if (numbers[m] == number) return m+1;
  13.     else
  14.     {
  15.         if (numbers[m] > number) {
  16.             r = m - 1;
  17.         }
  18.         else {
  19.             l = m + 1;
  20.         }
  21.     }
  22.   }
  23.  
  24.   return -1;
  25.  
  26. }
  27.  
  28. int main(void) {
  29.   long number_count;
  30.   std::cin >> number_count;
  31.   std::vector<long> numbers(number_count);
  32.   numbers.reserve(number_count);
  33.   for (auto &number:numbers) {
  34.     std::cin >> number;
  35.   }
  36.   assert(std::is_sorted(numbers.begin(), numbers.end()));
  37.  
  38.   long query_count;
  39.   std::cin >> query_count;
  40.   while (query_count-- > 0) {
  41.     long number;
  42.     std::cin >> number;
  43.     std::cout << get_pos(numbers, number) << " ";
  44.   }
  45.   std::cout << std::endl;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment