Find point of transition from 0 to 1 in an infinite sorted binary array

Problem

Given an infinite sorted array consisting only of 0s followed by 1s, find the index of the first occurrence of 1 (the transition point from 0 to 1).

Examples

Example 1

Input: array = [0, 0, 0, 0, 1, 1, 1, ...] (infinite)
Output: 4
Explanation: The first 1 appears at index 4.

Example 2

Input: array = [1, 1, 1, ...] (infinite)
Output: 0
Explanation: The first element is 1, so the transition point is index 0.

Example 3

Input: array = [0, 0, 0, ...] (infinite)
Output: -1
Explanation: There is no 1 in the array, so return -1.

Solution

Method 1 – Linear Search

Intuition

Check each element of arr one by one until you find the first 1. This is simple but inefficient for large arrays, as you may need to scan many elements before finding the transition point.

Approach

1. Start from index 0.
2. For each index i, check if arr[i] is 1.
3. Return the index i if found; otherwise, continue.
4. If no 1 is found (theoretically impossible in an infinite array, but for completeness), return -1.

Code

C++

class Solution {
public:
    int findTransition(const vector<int>& arr) {
        int i = 0;
        while (true) {
            if (arr[i] == 1) return i;
            i++;
        }
        return -1;
    }
};

Go

func findTransition(arr []int) int {
    for i := 0; ; i++ {
        if arr[i] == 1 {
            return i
        }
    }
    return -1
}

Java

class Solution {
    public int findTransition(int[] arr) {
        int i = 0;
        while (true) {
            if (arr[i] == 1) return i;
            i++;
        }
        // unreachable
        // return -1;
    }
}

Kotlin

class Solution {
    fun findTransition(arr: IntArray): Int {
        var i = 0
        while (true) {
            if (arr[i] == 1) return i
            i++
        }
        // unreachable
        // return -1
    }
}

Python

class Solution:
    def find_transition(self, arr: list[int]) -> int:
        i = 0
        while True:
            if arr[i] == 1:
                return i
            i += 1
        return -1

Rust

impl Solution {
    pub fn find_transition(arr: &[i32]) -> i32 {
        let mut i = 0;
        loop {
            if arr[i] == 1 {
                return i as i32;
            }
            i += 1;
        }
    }
}

TypeScript

class Solution {
    findTransition(arr: number[]): number {
        let i = 0;
        while (true) {
            if (arr[i] === 1) return i;
            i++;
        }
        // unreachable
        // return -1;
    }
}

Complexity

• ⏰ Time complexity: O(n) — Must scan every element up to the transition point.
• 🧺 Space complexity: O(1) — Only uses a constant amount of extra space.

Method 2 – Exponential Search + Binary Search

Intuition

Since the array is infinite and sorted, we can't use its length. Instead, we quickly find a range containing the transition point by jumping in powers of two for the index (right), then use binary search within that range (left to right).

Approach

1. Start at index 0.
2. If arr[0] == 1, return 0 immediately.
3. Otherwise, repeatedly check arr[right] for increasing right (i.e., 1, 2, 4, 8, ...), until you find arr[right] == 1.
4. Now, the transition point is between indices left and right (where left is the previous value of right).
5. Perform binary search in arr[left..right] to find the first 1:
   • For each mid = left + (right - left) // 2, if arr[mid] == 1, update ans = mid and search left half (right = mid - 1); else search right half (left = mid + 1).
6. If no 1 is found, return -1.

Code

C++

class Solution {
public:
    int findTransition(const vector<int>& arr) {
        if (arr[0] == 1) return 0;
        int left = 0, right = 1;
        while (arr[right] == 0) {
            left = right;
            right *= 2;
        }
        // Binary search between left+1 and right
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == 1) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};

Go

func findTransition(arr []int) int {
    if arr[0] == 1 {
        return 0
    }
    left, right := 0, 1
    for arr[right] == 0 {
        left = right
        right *= 2
    }
    ans := -1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == 1 {
            ans = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return ans
}

Java

class Solution {
    public int findTransition(int[] arr) {
        if (arr[0] == 1) return 0;
        int left = 0, right = 1;
        while (arr[right] == 0) {
            left = right;
            right *= 2;
        }
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == 1) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun findTransition(arr: IntArray): Int {
        if (arr[0] == 1) return 0
        var left = 0
        var right = 1
        while (arr[right] == 0) {
            left = right
            right *= 2
        }
        var ans = -1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (arr[mid] == 1) {
                ans = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return ans
    }
}

Python

class Solution:
    def find_transition(self, arr: list[int]) -> int:
        if arr[0] == 1:
            return 0
        left, right = 0, 1
        while arr[right] == 0:
            left = right
            right *= 2
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] == 1:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans

Rust

impl Solution {
    pub fn find_transition(arr: &[i32]) -> i32 {
        if arr[0] == 1 {
            return 0;
        }
        let (mut left, mut right) = (0, 1);
        while arr[right] == 0 {
            left = right;
            right *= 2;
        }
        let mut ans = -1;
        while left <= right {
            let mid = left + (right - left) / 2;
            if arr[mid] == 1 {
                ans = mid as i32;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    findTransition(arr: number[]): number {
        if (arr[0] === 1) return 0;
        let left = 0, right = 1;
        while (arr[right] === 0) {
            left = right;
            right *= 2;
        }
        let ans = -1;
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (arr[mid] === 1) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(log n) — Exponential search finds the range in O(log n), then binary search finds the transition in O(log n), where n is the index of the first 1.
• 🧺 Space complexity: O(1) — Only uses a constant amount of extra space.