Binary Searchable Numbers in an Unsorted Array

Binary Searchable Numbers in an Unsorted Array

What is this problem about?

The "Binary Searchable Numbers in an Unsorted Array interview question" is a subtle challenge about the mechanics of binary search. In a sorted array, every number is "searchable" (meaning a binary search will correctly find it). In an unsorted array, some numbers might still be "searchable" if they happen to be in a position that the binary search algorithm doesn't skip. A number at index $i$ is searchable if all elements to its left are smaller and all elements to its right are larger.

Why is this asked in interviews?

Google uses the "Binary Searchable Numbers in an Unsorted Array coding problem" to check if a candidate truly understands how binary search works, rather than just memorizing the code. It tests "Array interview pattern" skills, specifically the ability to use pre-calculation (prefix max and suffix min) to validate global properties in linear time.

Algorithmic pattern used

This problem is solved using the Prefix Maximum and Suffix Minimum pattern.

1. Left Constraint: A number is searchable only if it is greater than every number before it. Create an array prefix_max where prefix_max[i] is the maximum value from 0 to i-1.
2. Right Constraint: A number is searchable only if it is smaller than every number after it. Create an array suffix_min where suffix_min[i] is the minimum value from i+1 to n-1.
3. Validation: A number arr[i] is searchable if prefix_max[i] < arr[i] AND arr[i] < suffix_min[i]. Count how many indices satisfy both conditions.

Example explanation

Array: [1, 3, 2]

• Index 0 (Value 1): Max to left = $-\infty$, Min to right = 2. $1 < 2$. (Searchable)
• Index 1 (Value 3): Max to left = 1, Min to right = 2. $3 > 2$. (Not Searchable - binary search for 3 might look at index 2 and then go left, missing index 1).
• Index 2 (Value 2): Max to left = 3, Min to right = $+\infty$. $2 < 3$. (Not Searchable). Total searchable: 1.

Common mistakes candidates make

• Misunderstanding searchable: Thinking it means the number just needs to be in the "correct" sorted position. It actually means the number must act as a valid pivot for any possible binary search path.
• Nested Loops: Using $O(N^2)$ to check the left/right condition for every index.
• Ignoring Edge Cases: Failing to correctly handle the first and last elements.

Interview preparation tip

The pattern of "is $X$ the greatest so far and the smallest yet to come?" is a very common interview technique. Practice using "Monotonic Stack" or "Prefix/Suffix arrays" to solve these types of "boundary" problems.