LeetCode Solutions
702. Search in a Sorted Array of Unknown Size
Time: $O(\log 10^4)$ Space: $O(1)$
/**
* // 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 = 1e4;
while (l < r) {
const int m = (l + r) / 2;
if (reader.get(m) < target)
l = m + 1;
else
r = m;
}
return reader.get(l) == target ? l : -1;
}
};
/**
* // 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 = (int) 1e4;
while (l < r) {
final int m = (l + r) / 2;
if (reader.get(m) < target)
l = m + 1;
else
r = m;
}
return reader.get(l) == target ? l : -1;
}
}
# """
# 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 = 0
r = 10**4
while l < r:
m = (l + r) // 2
if reader.get(m) < target:
l = m + 1
else:
r = m
return l if reader.get(l) == target else -1