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:
ith index (0-indexed) of the secret array (i.e., secret[i]), or231 - 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 <= 104secret is sorted in a strictly increasing order.First, we define a pointer r = 1. Each time, we check if the value at position r is less than the target value. If it is, we multiply r by 2, i.e., shift it left by one bit, until the value at position r is greater than or equal to the target value. At this point, we can determine that the target value is within the interval [r / 2, r].
Next, we define a pointer l = r / 2, and then we can use the binary search method to find the position of the target value within the interval [l, r].
The time complexity is O(log M), where M is the position of the target value. The space complexity is O(1).
Java
C++
Go
TypeScript
Median of Two Sorted Arrays - Binary Search - Leetcode 4 • NeetCode • 551,893 views views
Watch 9 more video solutions →Practice Search in a Sorted Array of Unknown Size with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor