Advertisement
rudolf222222

Untitled

Nov 1st, 2022
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. bool BinarySearch(const int* begin, const int* end, int target) {
  4.   int mid = 0;
  5.   int begin_index = 0;
  6.   int end_index = 0;
  7.   int mid_index = 0;
  8.   end_index = end - begin;
  9.   while (end_index - begin_index > 1) {
  10.     mid = *(begin + (end_index + begin_index) / 2);
  11.     mid_index = (end_index + begin_index) / 2;
  12.     if (mid > target) {
  13.       end_index = mid_index;
  14.     } else if (mid < target) {
  15.       begin_index = mid_index;
  16.     } else if (mid == target) {
  17.       return true;
  18.     }
  19.   }
  20.   return (*(begin + begin_index) == target ||
  21.           *(begin + end_index - 1) == target);
  22. }
  23. int* ArrayInit() {
  24.   int arr_length = 0;
  25.   std::cin >> arr_length;
  26.   int* arr = new int[arr_length];
  27.   for (int i = 0; i < arr_length; ++i) {
  28.     std::cin >> arr[i];
  29.   }
  30.   return arr;
  31. }
  32. void SearchRequests(const int* arr){
  33.   int function_calls = 0;
  34.   std::cin >> function_calls;
  35.   int begin = 0;
  36.   int end = 0;
  37.   int target = 0;
  38.   for (int calls = 0; calls < function_calls; ++calls) {
  39.     std::cin >> begin >> end >> target;
  40.     if (BinarySearch(&arr[begin], &arr[end], target)) {
  41.       std::cout << "YES\n";
  42.     } else {
  43.       std::cout << "NO\n";
  44.     }
  45.   }
  46. }
  47. int main() {
  48.   int* arr = ArrayInit();
  49.   SearchRequests(arr);
  50.   delete[] arr;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement