Skip to content

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

Thinking

The array is sorted but its length is hidden; we may only probe indices, and out-of-range reads return a sentinel. A linear scan from \(0\) uses \(\Theta(M)\) calls and ignores order.

Without a known length we cannot binary-search the whole array. Exponentially growing a right bound until the value is at least the target traps the answer in an interval of size \(O(M)\).

Start from \(r=1\), double until the probe is large enough, then binary-search \([r/2, r]\). The number of API calls is \(O(\log M)\).

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# """
# 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: "ArrayReader", target: int) -> int:
        r = 1
        while reader.get(r) < target:
            r <<= 1
        l = r >> 1
        while l < r:
            mid = (l + r) >> 1
            if reader.get(mid) >= target:
                r = mid
            else:
                l = mid + 1
        return l if reader.get(l) == target else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * // This is ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *     public int get(int index) {}
 * }
 */

class Solution {
    public int search(ArrayReader reader, int target) {
        int r = 1;
        while (reader.get(r) < target) {
            r <<= 1;
        }
        int l = r >> 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (reader.get(mid) >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return reader.get(l) == target ? l : -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     int get(int index);
 * };
 */

class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int r = 1;
        while (reader.get(r) < target) {
            r <<= 1;
        }
        int l = r >> 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (reader.get(mid) >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return reader.get(l) == target ? l : -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * type ArrayReader struct {
 * }
 *
 * func (this *ArrayReader) get(index int) int {}
 */

func search(reader ArrayReader, target int) int {
    r := 1
    for reader.get(r) < target {
        r <<= 1
    }
    l := r >> 1
    for l < r {
        mid := (l + r) >> 1
        if reader.get(mid) >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    if reader.get(l) == target {
        return l
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * class ArrayReader {
 *      // This is the ArrayReader's API interface.
 *      // You should not implement it, or speculate about its implementation
 *      get(index: number): number {};
 *  };
 */

function search(reader: ArrayReader, target: number): number {
    let r = 1;
    while (reader.get(r) < target) {
        r <<= 1;
    }
    let l = r >> 1;
    while (l < r) {
        const mid = (l + r) >> 1;
        if (reader.get(mid) >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return reader.get(l) === target ? l : -1;
}

Comments