Search an Unbounded Sorted Array
Problem statement
You are given a list of distinct integers in increasing order, but you are not told where it ends. Reading any position past the last value gives 2147483647, which is larger than every real value.
Return the position (counting from 0) of target in the list, or -1 if it is not there. Aim for O(log p) reads, where p is the target's position (or where it would be).
In this exercise the list is passed as an ordinary array reader. Read it only through a small helper get(i) that returns reader[i], or 2147483647 when i is past the end, and do not use the array's length as a search bound.
Function
searchUnbounded(reader: int[], target: int) → intExamples
Example 1
reader = [-8,-3,1,4,10,15,22]target = 10return = 4The value 10 is at position 4 (counting from 0): -8, -3, 1, 4 come before it.
Example 2
reader = [2,6,9,13]target = 7return = -17 would sit between 6 and 9, but it is not in the list, so the answer is -1.
Example 3
reader = [5]target = 5return = 0The only value is the target, at position 0. Every read past it returns 2147483647.
Constraints
1 <= reader.length <= 5000-10^9 <= reader[i] <= 10^9, and the values are distinct and in increasing order-10^9 <= target <= 10^9