JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

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 $i^{th}$ 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.

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

Code

/**
 * // 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) {
        if (reader.get(0) == target) return 0;

        int right = 1;
        while (reader.get(right) < target) {
            right = right << 1;
        }

        // 取得左右边界
        int left = right >> 1;

        while (left + 1 < right) {
            int mid = (left + right) / 2;
            int num = reader.get(mid);

            if (num == target) return mid;
            if (num > target) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (reader.get(left) == target) return left;
        if (reader.get(right) == target) return right;

        return -1;
    }
}

Time complexity

$O(log⁡T)$, where T is an index of target value.

There are two operations here: to define search boundaries and to perform binary search.

Define search boundaries

Let’s first find the number of steps k to setup the boundaries. On the first step, the boundaries are $2^0 .. 2^{0+1}$;on the second step $2^1 .. 2^{1 + 1}$; When everything is done, the boundaries are $2^k .. 2^{k + 1}$ and $2^k < T < 2^{k + 1}$. That means one needs $k=log⁡T$ steps to setup the boundaries, that means $O(log⁡T)$ time complexity.

There are $2^{k + 1} - 2^k = 2^k$ elements in the boundaries, and $2^{logT}=T$, so the time complexity is $O(logT)$

$n=log_{a}b, a^n=b, => a^{log_{a}b}=b$