467. Find the Transition Point in 0s and 1s Array

Given a sorted binary array arr with all 0s followed by all 1s, find the index of the first 1 (the transition point). Return -1 if no 1 exists. Solve in O(log n).

Input: A sorted binary array of 0s and 1s.

Output: Index of the first 1, or -1 if all zeros.

Examples

Input: [0,0,0,1,1,1]
Output: 3
Explanation: First 1 is at index 3.

Input: [1,1,1,1]
Output: 0
Explanation: All 1s; transition point is index 0.

Input: [0,0,0,0]
Output: -1
Explanation: No 1s present; return -1.

Constraints

• 1 <= arr.length <= 10^6
• arr[i] is 0 or 1
• Sorted non-decreasing

Asked by