#include <bits/stdc++.h>
using namespace std;
int countBinarySearchableIndex(int Arr[], int l, int r,
int LR, int RL)
{
// Invalid indexes
if (l > r)
return 0;
int ans = 0;
// Finding the middle element of the current array
// (arr[l], ... arr[r]) Similar to as we do in binary
// search
int m = (l + r) / 2;
// If these conditions follow that means Arr[m] is
// binary searchable.
//cout<<LR<<" "<<m<<" "<<Arr[m]<<" "<<RL<<endl;
if (LR < Arr[m] && Arr[m] < RL) {
cout<<Arr[m]<<endl;
ans = 1;
}
// Finding the binary searchable elements to the left of
// middle(m) element
int l_ans = countBinarySearchableIndex(
Arr, l, m - 1, LR, min(RL, Arr[m]));
// Finding the binary searchable elements to the right
// of middle(m) element
int r_ans = countBinarySearchableIndex(
Arr, m + 1, r, max(LR, Arr[m]), RL);
return ans + l_ans + r_ans;
}
int main()
{
int Arr[] = { 2, 3, 1, 5, 8, 7, 9 };
int n = 7;
cout << "Number of Binary Searchable Indexes: ";
cout << countBinarySearchableIndex(Arr, 0, n - 1, -1e9,
1e9)
<< endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCgppbnQgY291bnRCaW5hcnlTZWFyY2hhYmxlSW5kZXgoaW50IEFycltdLCBpbnQgbCwgaW50IHIsCgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50IExSLCBpbnQgUkwpCnsKCiAgICAvLyBJbnZhbGlkIGluZGV4ZXMKCiAgICBpZiAobCA+IHIpCgogICAgICAgIHJldHVybiAwOwoKICAgIGludCBhbnMgPSAwOwogCgogICAgLy8gRmluZGluZyB0aGUgbWlkZGxlIGVsZW1lbnQgb2YgdGhlIGN1cnJlbnQgYXJyYXkKCiAgICAvLyAoYXJyW2xdLCAuLi4gYXJyW3JdKSBTaW1pbGFyIHRvIGFzIHdlIGRvIGluIGJpbmFyeQoKICAgIC8vIHNlYXJjaAoKICAgIGludCBtID0gKGwgKyByKSAvIDI7CiAKCiAgICAvLyBJZiB0aGVzZSBjb25kaXRpb25zIGZvbGxvdyB0aGF0IG1lYW5zIEFyclttXSBpcwoKICAgIC8vIGJpbmFyeSBzZWFyY2hhYmxlLgogICAgCiAgICAvL2NvdXQ8PExSPDwiICI8PG08PCIgIjw8QXJyW21dPDwiICI8PFJMPDxlbmRsOyAKCiAgICBpZiAoTFIgPCBBcnJbbV0gJiYgQXJyW21dIDwgUkwpIHsKICAgIAkKICAgIAljb3V0PDxBcnJbbV08PGVuZGw7IAoKICAgICAgICBhbnMgPSAxOwogICAgfQogCgogICAgLy8gRmluZGluZyB0aGUgYmluYXJ5IHNlYXJjaGFibGUgZWxlbWVudHMgdG8gdGhlIGxlZnQgb2YKCiAgICAvLyBtaWRkbGUobSkgZWxlbWVudAoKICAgIGludCBsX2FucyA9IGNvdW50QmluYXJ5U2VhcmNoYWJsZUluZGV4KAoKICAgICAgICBBcnIsIGwsIG0gLSAxLCBMUiwgbWluKFJMLCBBcnJbbV0pKTsKIAoKICAgIC8vIEZpbmRpbmcgdGhlIGJpbmFyeSBzZWFyY2hhYmxlIGVsZW1lbnRzIHRvIHRoZSByaWdodAoKICAgIC8vIG9mIG1pZGRsZShtKSBlbGVtZW50CgogICAgaW50IHJfYW5zID0gY291bnRCaW5hcnlTZWFyY2hhYmxlSW5kZXgoCgogICAgICAgIEFyciwgbSArIDEsIHIsIG1heChMUiwgQXJyW21dKSwgUkwpOwogCgogICAgcmV0dXJuIGFucyArIGxfYW5zICsgcl9hbnM7Cn0KIAoKaW50IG1haW4oKQp7CgogICAgaW50IEFycltdID0geyAyLCAzLCAxLCA1LCA4LCA3LCA5IH07CgogICAgaW50IG4gPSA3OwoKICAgIGNvdXQgPDwgIk51bWJlciBvZiBCaW5hcnkgU2VhcmNoYWJsZSBJbmRleGVzOiAiOwoKICAgIGNvdXQgPDwgY291bnRCaW5hcnlTZWFyY2hhYmxlSW5kZXgoQXJyLCAwLCBuIC0gMSwgLTFlOSwKCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDFlOSkKCiAgICAgICAgIDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0=