448. Find Position of Element in Infinite Sorted Array

Given a sorted array that is conceptually infinite (you cannot access its length) and a target, return the index of target or -1 if not found. Use exponential search to first bound the range, then binary search. For this problem the array is finite but treat its length as unknown.

Input: A sorted integer array arr (treat as infinite) and integer target.

Output: Index of target, or -1.

Examples

Input: [1,3,5,7,9,11,13,15], 7
Output: 3
Explanation: Expand window: [0,1]→[1,3]; [1,3]→[0,4)→... find 7 at index 3.

Input: [1,3,5,7,9,11,13,15], 6
Output: -1
Explanation: 6 not in array; return -1.

Input: [-10,-5,0,5,10,15,20], -10
Output: 0
Explanation: First element matches immediately.

Constraints

• 1 <= arr.length <= 10^5
• -10^9 <= arr[i] <= 10^9
• Sorted ascending
• All distinct

Asked by