> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Binary Searchable Numbers in an Unsorted Array

> Tested Python solution for LeetCode 1966 with 27 pytest cases. Generate a practice environment with lcpy.

LeetCode 1966, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Binary Search](/catalog/topics/binary-search), [Stack](/catalog/topics/stack), [Monotonic Stack](/catalog/topics/monotonic-stack). [View on LeetCode](https://leetcode.com/problems/binary-searchable-numbers-in-an-unsorted-array/description/).

Generate this problem as a practice environment: tested reference solution, 27 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1966   # by problem number
lcpy gen -s binary_searchable_numbers_in_an_unsorted_array   # by problem name
```

## Problem

\<p>Consider a function that implements an algorithm \<strong>similar\</strong> to \<a href="[https://leetcode.com/explore/learn/card/binary-search/](https://leetcode.com/explore/learn/card/binary-search/)" target="\_blank">Binary Search\</a>. The function has two input parameters: \<code>sequence\</code> is a sequence of integers, and \<code>target\</code> is an integer value. The purpose of the function is to find if the \<code>target\</code> exists in the \<code>sequence\</code>.\</p>

\<p>The pseudocode of the function is as follows:\</p>

\<pre>
func(sequence, target)
while sequence is not empty
\<strong>randomly\</strong> choose an element from sequence as the pivot
if pivot = target, return \<strong>true\</strong>
else if pivot \< target, remove pivot and all elements to its left from the sequence
else, remove pivot and all elements to its right from the sequence
end while
return \<strong>false\</strong>
\</pre>

\<p>When the \<code>sequence\</code> is sorted, the function works correctly for \<strong>all\</strong> values. When the \<code>sequence\</code> is not sorted, the function does not work for all values, but may still work for \<strong>some\</strong> values.\</p>

\<p>Given an integer array \<code>nums\</code>, representing the \<code>sequence\</code>, that contains \<strong>unique\</strong> numbers and \<strong>may or may not be sorted\</strong>, return \<em>the number of values that are \<strong>guaranteed\</strong> to be found using the function, for \<strong>every possible\</strong> pivot selection\</em>.\</p>

### Examples

```
Input: nums = [7]
Output: 1
Explanation:
Searching for value 7 is guaranteed to be found.
Since the sequence has only one element, 7 will be chosen as the pivot. Because the pivot equals the target, the function will return true.
```

```
Input: nums = [-1,5,2]
Output: 1
Explanation:
Searching for value -1 is guaranteed to be found.
If -1 was chosen as the pivot, the function would return true.
If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only -1 and the function would return true.
If 2 was chosen as the pivot, 2 would be removed. In the next loop, the sequence would have -1 and 5. No matter which number was chosen as the next pivot, the function would find -1 and return true.

Searching for value 5 is NOT guaranteed to be found.
If 2 was chosen as the pivot, -1, 5 and 2 would be removed. The sequence would be empty and the function would return false.

Searching for value 2 is NOT guaranteed to be found.
If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only -1 and the function would return false.

Because only -1 is guaranteed to be found, you should return 1.
```

### Constraints

* 1 \<= nums.length \<= 10\<sup>5\</sup>
* -10\<sup>5\</sup> \<= nums\[i] \<= 10\<sup>5\</sup>
* All the values of \<code>nums\</code> are \<strong>unique\</strong>.

\<p>\<strong>Follow-up:\</strong> If \<code>nums\</code> has \<strong>duplicates\</strong>, would you modify your algorithm? If so, how?\</p>

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/binary_searchable_numbers_in_an_unsorted_array/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/binary_searchable_numbers_in_an_unsorted_array/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(n)
    def binary_searchable_numbers(self, nums: list[int]) -> int:
        n = len(nums)
        searchable = [True] * n
        left_max = -(10**5 + 1)
        for i, value in enumerate(nums):
            if value < left_max:
                searchable[i] = False
            else:
                left_max = value
        right_min = 10**5 + 1
        total = 0
        for i in range(n - 1, -1, -1):
            if nums[i] > right_min:
                searchable[i] = False
            else:
                right_min = nums[i]
            if searchable[i]:
                total += 1
        return total
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.