#include<iostream>
#include<cmath>
using namespace std;

struct Array
{
    int *A;
    int size;
    int length;
};

void Display (struct Array arr1){
    int i;
    cout<<"\nThe elements are\n";
    for(i = 0; i<arr1.length; i++){
        cout<<arr1.A[i]<<"\n";
    }

}

// void Append(struct Array *arr1, int x) //since it is to append elements, pointer will be used to access address.
// {
//     if (arr1->length < arr1->size) // The Arrow(->) operator exists to access the members of the structure or the unions using pointers.
//         arr1->A[arr1->length++] = x;  
// }

void Insert(struct Array *arr1, int index, int x)
{
    int i;
    // if(arr1->length==arr1->size){return;}
    if (index>=0 && index<=arr1->length){
        for(i=arr1->length; i>index; i--){
            arr1->A[i]=arr1->A[i-1];
            
            
        }
        arr1->length++;
        arr1->A[index] = x;
    }

}

int Delete(struct Array *arr1, int index)
{
    int i;
    int x = 0;
    // if(arr1->length==arr1->size){return;}
    if (index >= 0 && index <= arr1->length)
    {
        x = arr1->A[index];
        for (i = index; i < arr1->length-1; i++)
        {
            arr1->A[i] = arr1->A[i + 1];   
        }
        arr1->length--;
        return x;
    }
    return 0;
}

void swap(int *x,int *y){
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int LinearSearch(struct Array *arr, int key){
    int i;
    for(i=0;i<arr->length;i++){
        if(key == arr->A[i]){
            swap(&arr->A[i],&arr->A[i-1]); //for move to front method replace A[i-1] with A[0]
            return i;
        }
    }
    return -1;
}

int BinarySearch(struct Array arr, int key){
 int l,h,mid;
 l=0;
 h = arr.length-1;

 while (l<=h)
 {
  mid = (l+h)/2;  /* code */
  if(key==arr.A[mid]){
    return mid;}
  else if(key<arr.A[mid]){
    h = mid-1;}
  else{
    l = mid+1;
  }
  }  
 }

int RBinSearch (int a[], int l, int h, int key)
{
    int mid = 0;

    if(l<=h){
        mid = floor((l + h) / 2); /* code */
        if (key == a[mid])
            return mid;
        
        else if (key < a[mid])
            return RBinSearch(a, l, mid-1, key);

        else 
            return RBinSearch(a, mid+1, h, key);
    }
    else
        return -1;
}

    int main()
{
    struct Array arr1;
    //struct Array arr1={{1,5,4,67,9},20,5} predfined array with no user input
    int n ,i;
    cout<<"Enter size of an array\n";
    cin>>arr1.size;
    arr1.A = new int [arr1.size];
    arr1.length = 0;

    cout<<"enter the number of elements\n";
    cin>>n;

    cout<<"enter all the elements\n";
    for(i = 0; i<n; i++){
        cin>>arr1.A[i];
    }

    arr1.length = n;
    // Insert(&arr1, 3, 56);


    //  Delete(&arr1,2);
    //  int result = Delete(&arr1, 2);
    //  cout<<"\n"<<"deleted element is" << result;

    //  int searchL = LinearSearch(&arr1,5);
    //  cout<<"\n The element is present in position : "<<searchL;

    // int searchB = BinarySearch(arr1, 10); //iterative method of binary search
    // cout<< "\nThe element is present in position : " << searchB;

    cout << "\nThe element is present in position : " << RBinSearch(arr1.A, 0, arr1.length-1, 5);

        // Append(&arr1, 67);

        // cout << "\n";
        // Display(arr1);

        return 0;
}