Infinite Array Search

MediumPython

Problem

A Deutsche Telekom network-monitoring component exposes a sorted, conceptually infinite array of non-negative integers through indexed access. The array is strictly increasing, but its length is unknown to the caller. Find the index of a target value without scanning the entire array.

For this exercise, nums is a finite prefix used to simulate the infinite array. Accessing an index outside nums returns None, representing an unavailable position beyond the populated prefix.

Formal Specification

Implement find_infinite_array(nums, target).

Input: nums, a strictly increasing list of non-negative integers representing the accessible prefix, and target, a non-negative integer.
Output: Return the zero-based index of target, or -1 if the target is not present.
Your search must first identify a range that could contain the target, then apply binary search within that range.

Constraints

1 <= len(nums) <= 10^6
0 <= nums[i] <= 10^18
nums[i] < nums[i + 1]
0 <= target <= 10^18
Return -1 when target is absent

Function Signature

def find_infinite_array(nums, target):

For this exercise, nums is a finite prefix used to simulate the infinite array. Accessing an index outside nums returns None, representing an unavailable position beyond the populated prefix.

Formal Specification

Implement find_infinite_array(nums, target).

Input: nums, a strictly increasing list of non-negative integers representing the accessible prefix, and target, a non-negative integer.
Output: Return the zero-based index of target, or -1 if the target is not present.
Your search must first identify a range that could contain the target, then apply binary search within that range.