465. Index of First 1 in Infinite Binary Sorted Array

Given a sorted binary array (0s followed by 1s) treated as conceptually infinite, find the index of the first occurrence of 1. Use exponential expansion to bound the window, then binary search. Return -1 if no 1 is present.

Input: A sorted binary array (0s then 1s), treat its length as unknown.

Output: Index of first 1, or -1 if none.

Examples

Input: [0,0,0,1,1,1,1]
Output: 3
Explanation: Expand window until arr[hi]=1. BS finds first 1 at index 3.

Input: [1,1,1,1,1]
Output: 0
Explanation: First element is already 1.

Input: [0,0,0,0,0,0,1]
Output: 6
Explanation: Expand to find bound, BS locates first 1 at index 6.

Constraints

• 1 <= arr.length <= 10^5
• arr[i] is 0 or 1
• Sorted: all 0s before 1s

Asked by