Find First One in Infinite Stream

# Find First One in Infinite Stream ## Difficulty Medium ## Tags `binary search`, `exponential search` ## Problem Statement You have access to an API `Stream` that returns `0`s and `1`s. The stream is sorted: it consists of a sequence of `0`s followed by a sequence of `1`s. The stream is potentially infinite, so you cannot determine its length beforehand. Find the index of the first `1` in the stream. ## Constraints - You can access the element at index `i` using `stream.get(i)`. - The stream always contains at least one `1`. - Indices are 0-based. - Achieve O(log N) time complexity where N is the index of the first `1`. ## Signatures ### Python ```python def get(index: int) -> int: pass ``` ### Java ```java public class Solution { public int get(int index) { return null; } } ``` ### Csharp ```csharp public class Solution { public int get(int index) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int get(int index) { } }; ``` ### C ```c int get(int index) { } ``` ### Ruby ```ruby def get(index) end ``` ### Perl ```perl sub get { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def get(index: Int): Int = { } } ``` ### Haskell ```haskell get :: ... -> ... get args = undefined ``` ### Clojure ```clojure (defn get [index] ) ``` ### Scheme ```scheme (define (get index) ) ``` ## Examples ### Example 1 **Input:** ``` stream = [0, 0, 0, 1, 1, 1, ...] ``` **Output:** ``` 3 ``` **Explanation:** The first 1 is at index 3. ### Example 2 **Input:** ``` stream = [1, 1, 1, ...] ``` **Output:** ``` 0 ``` **Explanation:** The first element is already 1. ### Example 3 **Input:** ``` stream = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, ...] ``` **Output:** ``` 10 ``` **Explanation:** Ten zeros before the first 1. ## Hints 1. Since the length is unknown, you cannot perform a standard binary search immediately. 2. First, find an upper bound `high` such that `stream.get(high) == 1`. 3. Use exponential search: check indices 1, 2, 4, 8, 16... until you find a 1. 4. Then perform binary search between `high/2` and `high`.