Anik_Akash

ans-2 binary serach

Oct 6th, 2021 (edited)
287
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace    std;
  3.  
  4. #define flush                    cin.ignore(numeric_limits<streamsize>::max(),'\n')
  5. #define FASTERIO                 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  6. #define NL                       cout<<'\n';
  7. #define pi                       acos(-1.0) //3.1415926535897932384626
  8. #define pb                       push_back
  9. #define mk                       make_pair
  10. #define mx                       1000005
  11. #define EPS                      1e-10
  12. #define dpoint(x)                fixed<<setprecision(x)
  13. # define my_sizeof(type) ((char *)(&type+1)-(char*)(&type))
  14. typedef long long int            ll;
  15. typedef double                   dl;
  16. typedef unsigned long long int   ull;
  17.  
  18.  
  19. void sort_ascending(int arr[], int n) {
  20.     for (int i = 0; i < n - 1; i++) {
  21.         for (int j = i + 1; j < n; j++) {
  22.             if (arr[i] > arr[j])swap(arr[i], arr[j]);
  23.         }
  24.     }
  25. }
  26. int binary_search(int arr[], int key) {
  27.     int low = 0, high = my_sizeof(arr)/my_sizeof(arr[0]);
  28.     high -=1;
  29.     while (low <= high) {
  30.         int mid = low + (high - low) / 2;
  31.         if (arr[mid] > key)high = mid - 1;
  32.         else if (arr[mid] < key) low = mid + 1;
  33.         else return mid;
  34.         }
  35.         return -1;
  36. }
  37.  
  38. int main() {
  39.  
  40. #ifdef anikakash
  41.     clock_t tStart = clock();
  42.     freopen("input.txt", "r", stdin);
  43.     freopen("tmp.txt", "w", stdout);
  44. #endif
  45.  
  46.     FASTERIO; //cmt when use scanf & printf ;
  47.  
  48.  
  49.     int n; cin >> n;
  50.     int arr[n + 1];
  51.     for(int i=0; i<n; i++)cin>>arr[i];
  52.     sort_ascending(arr, n);
  53.     int test; cin >> test;
  54.     while (test--) {
  55.         int key; cin >> key;
  56.         int ans = binary_search(arr, key);
  57.         if(ans!=-1)
  58.         cout<<key<<" is found at index "<<ans<<endl;
  59.         else cout<<key<<" is not found in the array"<<endl;
  60.     }
  61.  
  62.  
  63.  
  64. #ifdef anikakash
  65.     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
  66. #endif
  67.  
  68.     return 0;
  69. }
Add Comment
Please, Sign In to add comment