# 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
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