Count of elements that are binary searchable in the given array

Given an array arr[] consisting of N integers, the task is to find the maximum count of integers that are binary searchable in the given array.

Examples:

Input: arr[] = {1, 3, 2}
Output: 2
Explanation: arr[0], arr[1] can be found.

Input: arr[] = {3, 2, 1, 10, 23, 22, 21}
Output: 3
Explanation: arr[1], arr[3], arr[5] can be found using binary search irrespective of whether the array is sorted or not.

Approach: The given problem can be solved by searching for each element separately in the array using the Binary Search approach and increment the count of those integers that exist in the array. Follow the below steps to solve the problem:

• Make a variable count = 0, that will store the count of elements that are binary searchable.
• For each element perform the binary search in the range [0, N) as:
  • Initialize the variable l as 0 and r as N-1 and perform the binary search for arr[i].
  • For each iteration of the while loop till l is less than equal to r, calculate the mid-value denoted by (l + r)/2.
    • If arr[mid] equals arr[i] then increment count by 1.
    • If arr[mid] is less than arr[i], then change l as mid + 1.
    • Otherwise, change r as mid – 1.
• The final answer will be stored in the variable count.

Below is the implementation of the above approach:

3

Time Complexity: O(N*log(N))
Auxiliary Space: O(1)

Approach 2: This problem can also be solved in linear time complexity.

In the previous approach, we were checking if for all a[i] belonging to array a, it was binary searchable or not. The problem with this approach is that we were visiting some of the elements multiple times to check ordering conditions. Rather than doing, this while we are visiting a node, we can mark it as binary searchable or not binary searchable. When constructing a binary tree for the array, it should be noted that the traversal is towards the right, when the target element is greater than the root or towards the left, when the target element is smaller than the root element. Now, given a path, the target element should be greater than the maximum of all root nodes via which the path of searching deviated towards the right, and smaller than the minimum of all values via which the path deviated towards the left.

To better understand this, create a tree representation of the process of binary search on the array. For eg:

Conversion of the given array to Binary Search Tree

In the binary search technique, the root node is actually the middle element of all the elements in that subtree. For eg:
Node 5 is the middle element of array [2, 3, 1, 5, 8, 7, 9]
and Node 3 is the middle element of array [2, 3, 1]

Example:

Now, Let’s search for node 1 in the above array. So, target = 1

Initially, In Binary Search: left = 0, right = 6.

arr[] = {2, 3, 1,  5, 8, 7, 9}

First Iteration: middle = (left + right) / 2 = 3 (arr[3] = 5)

Comparing middle element with target.

Since 5 > 1, so, right = middle – 1 = 3 – 1 = 2.

arr[] = {2, 3, 1}

Second Iteration: middle = (0 + 2) / 2 = 1 (arr[1] = 3)

Comparing middle element with target.

Since 3 > 1, so right = middle – 1 = 1 – 1 = 0.

arr[] = {2}

Comparing middle element with target. The values don’t match.(arr[0]!=1)

Hence, 1 is not binary searchable.

The path needs to be traversed for node e to be binary searchable

In the above Figure, for node e to be binary searchable:

If we want to search e, then e must be greater than a and c because of BST (binary search tree) conventions. also, e must be smaller than b and d. If this is not the case, then e is not binary searchable.

So, we can summarise the condition as; 
1. e < min(b, d)
2. e > max(a, c)

Below is the implementation of the above approach:

Number of Binary Searchable Indexes: 9

Time Complexity: O(n)
Auxiliary Space: O(log n) taken by Recursion Stack