#include <iostream>
using namespace std;
 
int binarySearch(int arr[], int l, int r, int x) {
    if (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
 
int main() {
    int arr[] = {2, 4, 10, 20, 40};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if(result != -1)
        cout << "Element found at index " << result << endl;
    else
        cout << "Element not found" << endl;
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGJpbmFyeVNlYXJjaChpbnQgYXJyW10sIGludCBsLCBpbnQgciwgaW50IHgpIHsKICAgIGlmIChsIDw9IHIpIHsKICAgICAgICBpbnQgbWlkID0gbCArIChyIC0gbCkgLyAyOwogICAgICAgIGlmIChhcnJbbWlkXSA9PSB4KSByZXR1cm4gbWlkOwogICAgICAgIGlmIChhcnJbbWlkXSA+IHgpIHJldHVybiBiaW5hcnlTZWFyY2goYXJyLCBsLCBtaWQgLSAxLCB4KTsKICAgICAgICByZXR1cm4gYmluYXJ5U2VhcmNoKGFyciwgbWlkICsgMSwgciwgeCk7CiAgICB9CiAgICByZXR1cm4gLTE7Cn0KCmludCBtYWluKCkgewogICAgaW50IGFycltdID0gezIsIDQsIDEwLCAyMCwgNDB9OwogICAgaW50IG4gPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsKICAgIGludCB4ID0gMTA7CiAgICBpbnQgcmVzdWx0ID0gYmluYXJ5U2VhcmNoKGFyciwgMCwgbiAtIDEsIHgpOwogICAgaWYocmVzdWx0ICE9IC0xKQogICAgICAgIGNvdXQgPDwgIkVsZW1lbnQgZm91bmQgYXQgaW5kZXggIiA8PCByZXN1bHQgPDwgZW5kbDsKICAgIGVsc2UKICAgICAgICBjb3V0IDw8ICJFbGVtZW50IG5vdCBmb3VuZCIgPDwgZW5kbDsKICAgIHJldHVybiAwOwp9