SHARE
TWEET

quick sort and binary search

Kulesh Dec 20th, 2016 29 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. void swap (int &a, int &b) {
  6.    int c = 0;
  7.    c = a;
  8.    a = b;
  9.    b = c;
  10. }
  11. void  qs (int *arr, int low, int high){
  12.     int a = high;
  13.     int i = low - 1;
  14.     if (low < high) {
  15.        for (int j = low; j < high; j++){
  16.           if (arr[a] > arr[j])  {
  17.              i++;
  18.              swap (arr[i], arr[j]);
  19.           }
  20.        }
  21.        swap(arr[a], arr[i+1]);
  22.        qs (*&arr, low, i);
  23.        qs (*&arr, i+2, high);
  24.    }
  25. }
  26. void bs (int arr[], int k, int low, int high){
  27.     int x = high/2;
  28.     if (low < high){
  29.         if (arr[x] < k){
  30.             bs(arr, k, x+1, high);
  31.         } else if (arr[x] > k) {
  32.             bs(arr, k, low, x-1);
  33.         } else if (arr[x] == k) {
  34.             cout << " Found " << k << " at " << x+1;
  35.         }
  36.     } else if (low == high) {
  37.         if (arr[high] == k){
  38.             cout << " Found " << k << " at " << high+1;
  39.         } else {
  40.             cout << "Not Found";
  41.         }
  42.     }
  43. }
  44. int main() {
  45.     int n, s;
  46.     cout << "How many integers you want to input : ";
  47.     cin >> n;
  48.     int array[n];
  49.     for (int x = 0; x < n; x++){
  50.         cin >> array[x];
  51.     }
  52.     qs(array, 0, n-1);
  53.     cout << "Ouput of sorted array : ";
  54.     for (int x = 0; x < n; x++){
  55.         cout << array[x] << " ";
  56.     }
  57.     cout << endl << "Which element do you want to search for? ";
  58.     cin >> s;
  59.     bs (array, s, 0, n-1);
  60.     return 0;
  61. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top