# 702. Search in a Sorted Array of Unknown Size

• Time: $O(\log 10^4)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 /** * // This is the ArrayReader's API interface. * // You should not implement it, or speculate about its implementation * class ArrayReader { * public: * int get(int index); * }; */ class Solution { public: int search(const ArrayReader& reader, int target) { int l = 0; int r = 10'000; while (l < r) { const int m = (l + r) / 2; if (reader.get(m) >= target) r = m; else l = m + 1; } return reader.get(l) == target ? l : -1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /** * // This is ArrayReader's API interface. * // You should not implement it, or speculate about its implementation * interface ArrayReader { * public int get(int index) {} * } */ class Solution { public int search(ArrayReader reader, int target) { int l = 0; int r = 10000; while (l < r) { final int m = (l + r) / 2; if (reader.get(m) >= target) r = m; else l = m + 1; } return reader.get(l) == target ? l : -1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 # """ # This is ArrayReader's API interface. # You should not implement it, or speculate about its implementation # """ # Class ArrayReader: # def get(self, index: int) -> int: class Solution: def search(self, reader: 'ArrayReader', target: int) -> int: l = bisect.bisect_left(range(10**4), target, key=lambda m: reader.get(m)) return l if reader.get(l) == target else -1