LeetCode 702. Search in a Sorted Array of Unknown Size

Problem

LeetCode 702. Search in a Sorted Array of Unknown Size

1. 题目简述

题目不赘述了，具体点击链接查看。

2. 算法思路

这道题很有意思，数组的大小是未知的，因此，我们需要将其分解成两个子问题。第一，确定二分查找的子区间；第二，二分查找哦啊该区间。

首先，我们定义l = 0， r = 1，直到reader.get(l) <= target <= reader.get(r)。然后二分查找该区间。算法复杂度为O(logN)

/**
 * // 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;
        }
        
        // 两个子问题，第一个是确认左右边界。这里left初始化为0，right初始化为1，然后每次get右边界。如果右边界<target，那么left=right + 1,right = right * 2。找到合适的区间后再想办法做二分。
        int l = 0, r = 1;
        while (reader.get(r) < target) {
            l = r + 1;
            r = r * 2;
        }
        
        // 此时，target一定是在[l,r]之间
        while (l < r) {
            int mid = l + r >> 1;
            if (reader.get(mid) == target) {
                return mid;
            } else if (reader.get(mid) > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        if (reader.get(l) == target) {
            return l;
        }
        
        return -1;
    }
}