This is an interactive problem.
You have a sorted array of unique elements and an unknown size. You do not have an access to the array but you can use the
ArrayReader interface to access it. You can call
- returns the value at the
ithindex (0-indexed) of the secret array (i.e.,
231 - 1if the
iis out of the boundary of the array.
You are also given an integer
Return the index
k of the hidden array where
secret[k] == target or return
You must write an algorithm with
O(log n) runtime complexity.
Input: secret = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in secret and its index is 4.
Input: secret = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in secret so return -1.
1 <= secret.length <= 104
-104 <= secret[i], target <= 104
secretis sorted in a strictly increasing order.
First to find an index where its value is no less than the target. Then we can use a binary search to find the index of the target.
# """ # 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, target): """ :type reader: ArrayReader :type target: int :rtype: int """ end = 1 while reader.get(end) < target: end *= 2 start = 0 while start + 1 < end: mid = start + (end - start) // 2 if reader.get(mid) == target: return mid elif reader.get(mid) < target: start = mid else: end = mid if reader.get(start) == target: return start if reader.get(end) == target: return end return -1
- Time Complexity: O(log(T)), where T is the index of the target.
- Space Complexity: O(1).