702. 搜索长度未知的有序数组
这是一个交互问题。
您有一个升序整数数组，其长度未知。您没有访问数组的权限，但是可以使用 ArrayReader 接口访问它。你可以调用 ArrayReader.get(i):
返回数组第ith个索引(0-indexed)处的值(即secret[i])，或者
如果 i 超出了数组的边界，则返回 231 - 1
你也会得到一个整数 target。
如果存在secret[k] == target，请返回索引 k 的值；否则返回 -1
你必须写一个时间复杂度为 O(log n) 的算法。
示例 1：
输入:secret= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 存在在 nums 中，下标为 4
示例 2：
输入:secret= [-1,0,3,5,9,12],target= 2 输出: -1 解释: 2 不在数组中所以返回 -1
提示：
1 <= secret.length <= 104-104 <= secret[i], target <= 104secret 严格递增相似题目
原站题解
golang 解法, 执行用时: 28 ms, 内存消耗: 6.5 MB, 提交时间: 2023-10-21 18:36:38
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* type ArrayReader struct {
* }
*
* func (this *ArrayReader) get(index int) int {}
*/
func search(reader ArrayReader, target int) int {
l,r:=0,10000
for l<=r{
mid:=l+(r-l)/2
if reader.get(mid)==target{
return mid
}else if reader.get(mid)>target{
r = mid-1
}else{
l = mid+1
}
}
return -1
}
python3 解法, 执行用时: 52 ms, 内存消耗: 17.1 MB, 提交时间: 2023-10-21 18:36:07
# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#class ArrayReader:
# def get(self, index: int) -> int:
ceil = 2**31 - 1
class Solution:
def search(self, reader: 'ArrayReader', target: int) -> int:
# 按照数组最大的可能性设置左右边界
left = 0
right = 20000
while left < right:
mid = (left + right + 1) >> 1 # 右中位数
if reader.get(mid) == 2147483647: # 如果越界，则右边界收缩
right = mid - 1
elif reader.get(mid) > target: # 如果大于目标值，则右边界收缩
right = mid - 1
else:
left = mid
return left if reader.get(left) == target else -1 # 返回结果
cpp 解法, 执行用时: 24 ms, 内存消耗: 10.1 MB, 提交时间: 2023-10-21 18:35:28
/**
* // 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 index = 0;
while (reader.get(index) != 2147483647) {
if (reader.get(index) == target)
return index;
index ++;
}
return -1;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 17 MB, 提交时间: 2023-10-21 18:34:49
# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#class ArrayReader:
# def get(self, index: int) -> int:
ceil = 2**31 - 1
class Solution:
def search(self, reader: 'ArrayReader', target: int) -> int:
i = 0
j = 10**4 - 1
while i < j - 1:
mid = i + (j - i) // 2
check = reader.get(mid)
if check == ceil or check > target:
j = mid
elif check < target:
i = mid
else:
return mid
if reader.get(i) == target:
return i
if reader.get(j) == target:
return j
return -1
java 解法, 执行用时: 1 ms, 内存消耗: 43.5 MB, 提交时间: 2023-10-21 18:34:13
/**
* // 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 {
private static final int MAX_LENGTH = 20000;
public int search(ArrayReader reader, int target) {
int left = 0;
int right = MAX_LENGTH - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midValue = reader.get(mid);
if (midValue < target) {
left = mid + 1;
} else if (midValue > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
}