// 2) WAP to implement binary search
#include <iostream>
using namespace std;

int main(){
    
    cout<<"Enter the size of the sorted array: ";
    int n;
    cin>>n;
    int arr[n];
    cout<<"Enter the array elements: ";
    for(int i=0;i<n;i++) {
        cin>>arr[i];
    }

    cout<<"Enter the element to be searched: ";
    int element;
    cin>>element;
    int index=-1;
    int low=0,high=n-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(arr[mid]==element){
            index=mid;
            break;
        }
        else if(arr[mid]>element) high=mid-1;
        else low=mid+1;
    }

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

    
    return 0;
}
/*
    OUTPUT:
    Enter the size of the sorted array: 5
    Enter the array elements: 4 5 10 12 33
    Enter the element to be searched: 4
    Element found at index: 0
*/