inhuman_Arif

Find element using binary search and sort using insertion sort

Oct 28th, 2021
614
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. void insertionsort(int arr[],int n)
  7. {
  8.     for (int i = 1; i < n; i++)
  9.     {
  10.         int key = arr[i];
  11.         int j = i - 1;
  12.         while (j >= 0 && arr[j] > key)
  13.         {
  14.             arr[j + 1] = arr[j];
  15.             j = j - 1;
  16.         }
  17.         arr[j + 1] = key;
  18.     }
  19. }
  20.  
  21. void binarysearch(int arr[],int n, int key)
  22. {
  23.     int low = 0, high = n-1;
  24.     bool flag = false;
  25.     while(low<=high)
  26.     {
  27.         int mid = (high+low)/2;
  28.         if(arr[mid]==key)
  29.         {
  30.             flag = true;
  31.             break;
  32.         }
  33.         if(arr[mid]<key)
  34.             low = mid+1;
  35.         else if(arr[mid]>key)
  36.             high = mid-1;
  37.     }
  38.     if(flag)
  39.         cout << "Found" << endl;
  40.     else
  41.         cout << "Not Found" << endl;
  42. }
  43.  
  44. int main()
  45. {
  46.     #ifndef ONLINE_JUDGE
  47.         freopen("input.txt", "r", stdin);
  48.         freopen("output.txt", "w", stdout);
  49.     #endif
  50.  
  51.     int n;
  52.     cin >> n;
  53.     int arr[n];
  54.     for(int i=0;i<n;i++)
  55.         cin >> arr[i];
  56.     //insertion sort
  57.     insertionsort(arr,n);
  58.     for(int i=0;i<n;i++)
  59.         cout << arr[i] << " ";
  60.     cout << endl;
  61.    
  62.     int key;
  63.     cin >> key;
  64.     binarysearch(arr,n,key);
  65.    
  66.    
  67.     return 0;
  68. }
RAW Paste Data