Search target in unknown-length sorted array
Overview
This question evaluates algorithm design and implementation skills for search algorithms on array-like interfaces with unknown length, focusing on bounds discovery, handling out-of-bounds sentinels, duplicate elements, and rigorous time and space complexity analysis.
You have read-only access to a sorted, increasing array-like interface of unknown length that supports get(i), which returns a valid integer for in-bounds i and a sentinel (e.g., +∞ or None) when i is out of bounds. Given a target value k, design an algorithm to find the index of k if it exists, otherwise return −1. Optimize time complexity, describe the approach to discover an upper bound, and handle duplicates by returning the first occurrence. Analyze time and space complexity.