Advertisement
rudolf222222

Untitled

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