Binary Searchable Count Count Binary Searchable Elements in an Unsorted Array

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

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:

Binary Search
Divide and Conquer
Recursive Range Constraints
Implicit Binary Search Trees
Value-Based Validation

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.