Search in a Sorted Array of Unknown Size

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 157 ms)

Metric	Value
Runtime	157 ms
Memory	40.4 MB
Date	2021-11-26

Solution

/**
 * // This is 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(ArrayReader reader, int target) {
        int lo = 0, hi = 1;
        while(reader.Get(hi)<target)
        {
            hi = hi * 2;
        }
        lo = hi /2;
        
        while(lo <= hi)
        {
            int mid = lo + (hi-lo)/2;
            if(reader.Get(mid) == target)
            {
                return mid;
            }
            else if(reader.Get(mid) > target)
            {
                hi = mid-1;
            }
            else
            {
                lo = mid+1;
            }
        }
        
        return -1;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed