#include <iostream>
using namespace std;


class binarysearch {
    private:
        int n;
    public:
    
    void bubblesort(int arr[], int size){
        n = size;
        for (int i=0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        
    }
    
    int search(int arr[], int x, int low, int high) {
        
      if (high >= low) {
        int mid = low + (high - low) / 2;
    
        // If found at mid, then return it
        if (arr[mid] == x)
          return mid;
    
        // Search the left half
        if (arr[mid] > x)
          return search(arr, x, low, mid - 1);
    
        // Search the right half
        return search(arr, x, mid + 1, high);
      }

  return -1;
}
};

int main() {
    int size, x;
    
    cout << "Enter the size of the 1-d array: ";
    cin >> size;
    int arr[size];
    
    cout << "Enter all the elements separated with spaces\n";
    for(int i=0; i<size; i++){
        cin>>arr[i];
    }
    
    cout <<"Enter the element to do binary search: ";
    cin >>x;

    binarysearch bs;
    bs.bubblesort(arr, size);
    
    cout<<"To do binary search, the array should be sorted\nThe sorted array is:\n";
    for(int i=0; i<size; i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    
    int index = bs.search(arr, x, 0, size - 1);

    if (index == -1) {
        cout << "Element not found" << endl;
    } else {
        cout << "Element "<<x<<" found at index " << index << endl;
    }

    return 0;
}