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

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
3

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

func findTransition(arr []int) int {
    for i := 0; ; i++ {
        if arr[i] == 1 {
            return i
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int findTransition(int[] arr) {
        int i = 0;
        while (true) {
            if (arr[i] == 1) return i;
            i++;
        }
        // unreachable
        // return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun findTransition(arr: IntArray): Int {
        var i = 0
        while (true) {
            if (arr[i] == 1) return i
            i++
        }
        // unreachable
        // return -1
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def find_transition(self, arr: list[int]) -> int:
        i = 0
        while True:
            if arr[i] == 1:
                return i
            i += 1
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn find_transition(arr: &[i32]) -> i32 {
        let mut i = 0;
        loop {
            if arr[i] == 1 {
                return i as i32;
            }
            i += 1;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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.