Given an array, find the number of "binary searchable" elements in the array.
A binary searchable element means that the element can be searched using binary searching tecnique no matter what the value of k in the algorithm below is, where 0 < k < 1.
// A is the array of elements
// n is the size of array
// x is the element to be searched
// k is a parameter that varies from 0 to 1
bool binary_search(int A, int n, int x, double k)
int u = 0, v = n-1;
while(u <= v)
int m = u + k*(v-u);
if(A[m] > x)
v = m-1;
else if(A[m] < x)
u = m+1;
The first line contains a single integer T, the number of test cases. T test cases follow each containing 2 lines, first of which contains a single integer N, the size of the array. Second line contains N integers which are the elements of the array.
Output one line for each test case each containing a single number that being the number of binary searchable elements.
T <= 10
1 <= N <= 10^5
All numbers in the array are 32-bit positive integers.
All numbers are distinct.
1 5 3 6 8
6 8 2 9 12 10
For the first test case, 1 6 8 are binary searchable.
For the second test case, only 9 binary searchable.
Problem Setter : Shikhar Sharad
Problem Tester: Shradha Chhaparia