Problem

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 2^31 - 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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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 <= 10^4
  • -10^4 <= secret[i], target <= 10^4
  • secret is sorted in a strictly increasing order.

Solution

Method 1 - Exponential Search + Binary Search

Intuition

Since the array size is unknown, we first find an upper bound for the index where the target could be by exponentially increasing the index until we go out of bounds or pass the target. Then, we perform binary search in that range.

Approach

  1. Start with right = 1, double it until ArrayReader.get(right) >= target or out of bounds.
  2. Perform binary search between left = 0 and right.
  3. If ArrayReader.get(mid) == target, return mid; else adjust bounds as usual.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// The ArrayReader interface is provided by the problem
class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int left = 0, right = 1;
        while (reader.get(right) < target) right <<= 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = reader.get(mid);
            if (val == target) return mid;
            else if (val > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// type ArrayReader interface { Get(index int) int }
func search(reader ArrayReader, target int) int {
    left, right := 0, 1
    for reader.Get(right) < target { right <<= 1 }
    for left <= right {
        mid := left + (right-left)/2
        val := reader.Get(mid)
        if val == target { return mid }
        if val > target { right = mid-1 } else { left = mid+1 }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// interface ArrayReader { int get(int index); }
class Solution {
    public int search(ArrayReader reader, int target) {
        int left = 0, right = 1;
        while (reader.get(right) < target) right <<= 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = reader.get(mid);
            if (val == target) return mid;
            else if (val > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// interface ArrayReader { fun get(index: Int): Int }
class Solution {
    fun search(reader: ArrayReader, target: Int): Int {
        var left = 0
        var right = 1
        while (reader.get(right) < target) right = right shl 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            val v = reader.get(mid)
            when {
                v == target -> return mid
                v > target -> right = mid - 1
                else -> left = mid + 1
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# class ArrayReader:
#     def get(self, index: int) -> int:
def search(reader, target):
    left, right = 0, 1
    while reader.get(right) < target:
        right <<= 1
    while left <= right:
        mid = (left + right) // 2
        val = reader.get(mid)
        if val == target:
            return mid
        elif val > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// trait ArrayReader { fn get(&self, index: i32) -> i32; }
pub fn search(reader: &impl ArrayReader, target: i32) -> i32 {
    let (mut left, mut right) = (0, 1);
    while reader.get(right) < target { right <<= 1; }
    while left <= right {
        let mid = left + (right - left) / 2;
        let val = reader.get(mid);
        if val == target { return mid; }
        if val > target { right = mid - 1; } else { left = mid + 1; }
    }
    -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// interface ArrayReader { get(index: number): number }
function search(reader: ArrayReader, target: number): number {
    let left = 0, right = 1;
    while (reader.get(right) < target) right <<= 1;
    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        const val = reader.get(mid);
        if (val === target) return mid;
        if (val > target) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)