# 702. Search in a Sorted Array of Unknown Size

## Description

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 ArrayReader.get(i) that:

• returns the value at the ith index (0-indexed) of the secret array (i.e., secret[i]), or
• returns 231 - 1 if the i is out of the boundary of the array.

You are also given an integer target.

Return the index k of the hidden array where secret[k] == target or return -1 otherwise.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: secret = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in secret and its index is 4.


Example 2:

Input: secret = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in secret so return -1.


Constraints:

• 1 <= secret.length <= 104
• -104 <= secret[i], target <= 104
• secret is sorted in a strictly increasing order.

## Solutions

• /**
* // This is ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
*     public int get(int index) {}
* }
*/

class Solution {
int left = 0, right = 20000;
while (left < right) {
int mid = left + right >> 1;
right = mid;
} else {
left = mid + 1;
}
}
return reader.get(left) == target ? left : -1;
}
}

• /**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
*   public:
*     int get(int index);
* };
*/

class Solution {
public:
int left = 0, right = 20000;
while (left < right) {
int mid = left + right >> 1;
right = mid;
} else {
left = mid + 1;
}
}
return reader.get(left) == target ? left : -1;
}
};

• # """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#    def get(self, index: int) -> int:

class Solution:
"""
:type target: int
:rtype: int
"""
left, right = 0, 20000
while left < right:
mid = (left + right) >> 1
right = mid
else:
left = mid + 1
return left if reader.get(left) == target else -1


• /**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* }
*
* func (this *ArrayReader) get(index int) int {}
*/

left, right := 0, 20000
for left < right {
mid := (left + right) >> 1
right = mid
} else {
left = mid + 1
}
}
return left
}
return -1
}

• /**
*		// This is the ArrayReader's API interface.
*		// You should not implement it, or speculate about its implementation
*		get(index: number): number {};
*  };
*/

let r = 1;
r <<= 1;
}
let l = r >> 1;
while (l < r) {
const mid = (l + r) >> 1;