Search in a Sorted Array of Unknown Size
Given an integer array sorted in ascending order, write a function to searchtarget
innums
. Iftarget
exists, then return its index, otherwise return-1
.However, the array size is unknown to you. You may only access the array using anArrayReader
interface, where ArrayReader.get(k)
returns the element of the array at indexk
(0-indexed).
You may assume all integers in the array are less than 10000
, and if you access the array out of bounds,ArrayReader.get
will return2147483647
.
Example 1:
Input:
array
= [-1,0,3,5,9,12],
target
= 9
Output:
4
Explanation:
9 exists in
nums
and its index is 4
Example 2:
Input:
array
= [-1,0,3,5,9,12],
target
= 2
Output:
-1
Explanation:
2 does not exist in
nums
so return -1
Note:
You may assume that all elements in the array are unique.
The value of each element in the array will be in the range
[-9999, 9999]
.
Analysis
隐含条件是数组下标index最大是Integer.MAX_VALUE
,最简单的想法就是right
设为Integer.MAX_VALUE
,然后进行常规的Binary Search。
更好的方法是利用reader.get(hi) < target
int hi = 1;
while (reader.get(hi) < target) {
hi = hi * 2;
}
int low = hi / 2;
这样保持了reader.get(hi) > target
, reader.get(low) < target
Solution
Binary Search - Template #3 (end = Integer.MAX_VALUE) - (5 ms, faster than 17.24%)
class Solution {
public int search(ArrayReader reader, int target) {
int start = 0, end = Integer.MAX_VALUE;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == reader.get(mid)) {
return mid;
} else if (target < reader.get(mid)) {
end = mid - 1;
} else {
start = mid + 1;
}
}
if (reader.get(start) == target) {
return start;
} else if (reader.get(end) == target) {
return end;
}
return -1;
}
}
Binary Search - Template #1 (hi = hi * 2 while val < target)
class Solution {
public int search(ArrayReader reader, int target) {
int hi = 1;
while (reader.get(hi) < target) {
hi = hi * 2;
}
int low = hi / 2;
while (low <= hi) {
int mid = low + (hi - low) / 2;
int val = reader.get(mid);
if (val == target) {
return mid;
} else if ( val > target) {
hi = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
}
Last updated
Was this helpful?