Problem Statement
Given an array of distinct integers, count how many elements can be successfully found using the standard binary search algorithm on the array itself, even though the array is not necessarily sorted.
A number is called binary searchable if running binary search for that value eventually reaches its index and returns success.
Example 1
Input
arr = [1, 3, 2]
Searching for 3
l = 0, r = 2
mid = 1
arr[mid] = 3
Found!
So 3 is binary searchable.
Searching for 2
l = 0, r = 2
mid = 1
arr[mid] = 3 > 2
r = 0
Search ends
Index 2 is never visited.
Therefore:
Binary searchable elements = {1, 3}
Answer = 2
Key Observation
Binary search does not visit every index.
For an element to be found, every comparison made before reaching it must direct the search toward its index.
Suppose binary search is trying to reach position i.
If a Midpoint Lies on the Left of i
mid < i
Then:
arr[mid] < arr[i]
must be true.
Otherwise, binary search would move left and never reach i.
If a Midpoint Lies on the Right of i
mid > i
Then:
arr[mid] > arr[i]
must be true.
Otherwise, binary search would move right and skip i.
Thinking in Reverse
Instead of checking every element individually, construct the binary-search recursion tree.
For every subarray:
[l ... r]
Binary search first examines:
mid = (l + r) / 2
This midpoint imposes restrictions on all searchable elements.
Left Subtree
All searchable elements must satisfy:
< arr[mid]
because reaching them requires moving left.
Right Subtree
All searchable elements must satisfy:
> arr[mid]
because reaching them requires moving right.
Thus, each recursive segment maintains a valid range:
(low, high)
An element is binary searchable if and only if:
low < arr[i] < high
Example Walkthrough
Input
arr = [2, 1, 3, 5, 4, 6]
Root Segment
mid = 2
arr[mid] = 3
Allowed range:
(-∞, +∞)
Since 3 lies within the range, it is searchable.
Left Segment
[2, 1]
Allowed range:
(-∞, 3)
Midpoint:
arr[0] = 2
2 is searchable.
Right Segment
[5, 4, 6]
Allowed range:
(3, +∞)
Midpoint:
arr[4] = 4
4 is searchable.
Continuing the recursion gives:
3 searchable elements
Answer
3
Algorithm
Perform a DFS on the implicit binary-search tree.
For each segment:
Find the midpoint.
Check whether the midpoint value lies inside the allowed range.
Recurse into the left subtree with an updated upper bound.
Recurse into the right subtree with an updated lower bound.
Correctness Proof
Let the current segment have a valid range:
(low, high)
Case 1: Left Subtree
To reach any index in the left subtree, binary search must move left at the current midpoint.
Therefore, target values must satisfy:
target < arr[mid]
Hence, the new range becomes:
(low, arr[mid])
Case 2: Right Subtree
To reach any index in the right subtree, binary search must move right.
Therefore:
target > arr[mid]
Hence, the new range becomes:
(arr[mid], high)
An element is searchable if and only if it satisfies every restriction imposed by all ancestors in the recursion tree.
The algorithm checks exactly these constraints.
Therefore, the algorithm is correct.
Why This Approach Works
Every midpoint acts like a decision point in binary search.
If an element violates the value constraints imposed by any ancestor midpoint, binary search will eventually move in the wrong direction and never reach that element.
By maintaining valid value ranges during recursion, we efficiently identify exactly those elements that binary search can successfully locate.
Java Solution
class Solution {
private int[] arr;
private int ans;
private void solve(int l, int r, int low, int high) {
if (l > r) return;
int mid = (l + r) / 2;
if (arr[mid] > low && arr[mid] < high) {
ans++;
}
solve(l, mid - 1, low, Math.min(high, arr[mid]));
solve(mid + 1, r, Math.max(low, arr[mid]), high);
}
public int binarySearchable(int[] arr) {
this.arr = arr;
this.ans = 0;
solve(
0,
arr.length - 1,
Integer.MIN_VALUE,
Integer.MAX_VALUE
);
return ans;
}
}
Dry Run
Input
arr = [1, 3, 2]
Root
mid = 1
arr[mid] = 3
Allowed range:
(-∞, +∞)
3 is searchable.
Left Subtree
[1]
Allowed range:
(-∞, 3)
1 is searchable.
Right Subtree
[2]
Allowed range:
(3, +∞)
2 does not satisfy the range condition.
Therefore:
Answer = 2
Complexity Analysis
Time Complexity
Each index is processed exactly once.
O(n)
Auxiliary Space
The recursion depth equals the height of the binary-search tree.
O(log n)
for a balanced recursion tree.
Pattern Recognition
This problem combines several important concepts:
A key insight is that we are not actually performing binary search for every element. Instead, we analyze the structure of binary search itself and determine which elements satisfy all required comparison constraints.
Key Takeaway
An element is binary searchable if it satisfies every decision that binary search would make on the path to its index. By viewing the array as an implicit binary-search recursion tree and maintaining valid value ranges, we can identify all searchable elements in linear time without running binary search separately for each value.
Summary
To count binary searchable elements, recursively build the binary-search decision tree and maintain the valid value range imposed by ancestor midpoints. An element is searchable only if its value lies within all inherited constraints. This transforms a potentially expensive per-element simulation into an elegant O(n) divide-and-conquer solution with O(log n) auxiliary space.