fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. int countBinarySearchableIndex(int Arr[], int l, int r,
  8.  
  9.                                int LR, int RL)
  10. {
  11.  
  12.     // Invalid indexes
  13.  
  14.     if (l > r)
  15.  
  16.         return 0;
  17.  
  18.     int ans = 0;
  19.  
  20.  
  21.     // Finding the middle element of the current array
  22.  
  23.     // (arr[l], ... arr[r]) Similar to as we do in binary
  24.  
  25.     // search
  26.  
  27.     int m = (l + r) / 2;
  28.  
  29.  
  30.     // If these conditions follow that means Arr[m] is
  31.  
  32.     // binary searchable.
  33.  
  34.     if (LR < Arr[m] && Arr[m] < RL)
  35.  
  36.         ans = 1;
  37.  
  38.  
  39.     // Finding the binary searchable elements to the left of
  40.  
  41.     // middle(m) element
  42.  
  43.     int l_ans = countBinarySearchableIndex(
  44.  
  45.         Arr, l, m - 1, LR, min(RL, Arr[m]));
  46.  
  47.  
  48.     // Finding the binary searchable elements to the right
  49.  
  50.     // of middle(m) element
  51.  
  52.     int r_ans = countBinarySearchableIndex(
  53.  
  54.         Arr, m + 1, r, max(LR, Arr[m]), RL);
  55.  
  56.  
  57.     return ans + l_ans + r_ans;
  58. }
  59.  
  60.  
  61. int main()
  62. {
  63.  
  64.     int Arr[] = { 10, 1,  2, 3, 4,  8,  6, 5,
  65.  
  66.                   7,  12, 9, 8, 13, 15, 11 };
  67.  
  68.     int n = 15;
  69.  
  70.     cout << "Number of Binary Searchable Indexes: ";
  71.  
  72.     cout << countBinarySearchableIndex(Arr, 0, n - 1, -1e9,
  73.  
  74.                                        1e9)
  75.  
  76.          << endl;
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0.01s 5556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Number of Binary Searchable Indexes: 9
https://ideone.com/0721Qw
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!