Solution Approach

The solution implements a binary search algorithm to find the smallest index where arr[i] == i.

Feasible Condition: arr[mid] >= mid - Is the value at mid at or ahead of the index?

This creates a pattern: [false, false, ..., true, true, true]

We want to find the first true index, then verify if it's exactly a fixed point (arr[i] == i, not just arr[i] >= i).

Binary Search Using Template:

1. Initialize: left = 0, right = len(arr) - 1, first_true_index = -1

2. Loop while left <= right:

   • Calculate mid = (left + right) // 2
   • If arr[mid] >= mid (feasible):
     • Record first_true_index = mid
     • Search left for potentially smaller index: right = mid - 1
   • Else (not feasible):
     • Search right: left = mid + 1

3. Why this works: When arr[mid] >= mid:

   • If arr[mid] == mid, then mid could be our answer, but there might be a smaller fixed point to the left
   • If arr[mid] > mid, there still might be a fixed point to the left where the value "catches down" to the index

4. Final check: After the loop, verify if first_true_index != -1 and arr[first_true_index] == first_true_index:

   • If true, return first_true_index as the smallest fixed point
   • If false, return -1 indicating no fixed point exists

The algorithm guarantees finding the smallest index because we continue searching left (right = mid - 1) even after finding a feasible position.

Time Complexity: O(log n) due to binary search Space Complexity: O(1) as we only use a constant amount of extra space

Example Walkthrough

Let's walk through the algorithm with arr = [-10, -5, 0, 3, 7].

We're looking for the smallest index i where arr[i] == i.

Initial Setup:

• left = 0, right = 4, first_true_index = -1
• Feasible condition: arr[mid] >= mid
• Array visualization with indices:

Index: 0    1   2  3  4
Value: -10  -5  0  3  7

Iteration 1:

• left = 0, right = 4
• mid = (0 + 4) // 2 = 2
• Check arr[2] = 0 >= mid = 2? → 0 >= 2 is FALSE
• Not feasible, search right: left = 3

Iteration 2:

• left = 3, right = 4
• mid = (3 + 4) // 2 = 3
• Check arr[3] = 3 >= mid = 3? → 3 >= 3 is TRUE
• Feasible! Record first_true_index = 3
• Search left for smaller: right = 2

Iteration 3:

• left = 3, right = 2
• left > right, loop terminates

Final Check:

• first_true_index = 3
• Check if arr[3] == 3? → Yes!
• Return 3

The algorithm correctly identifies that index 3 is the smallest (and only) index where the value equals the index.

Why Binary Search Works Here: Notice how at each step, we eliminated half of the search space:

• When arr[2] = 0 < 2, we knew indices 0, 1, 2 couldn't be fixed points (values are too small)
• When arr[3] = 3 >= 3, we found our potential answer and continued searching left for any smaller fixed point

The sorted and distinct nature of the array ensures that once values fall behind indices (arr[i] < i), they can never catch up when moving left, making binary search possible.

Time and Space Complexity

Time Complexity: O(log n)

The algorithm uses binary search to find the fixed point (where arr[i] == i). In each iteration, the search space is halved by comparing the middle element with its index:

• If arr[mid] >= mid, the fixed point (if it exists) must be in the left half including mid, so we set right = mid
• If arr[mid] < mid, the fixed point must be in the right half, so we set left = mid + 1

Since the search space is reduced by half in each iteration, and we continue until left >= right, the total number of iterations is O(log n) where n is the length of the array.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for the variables left, right, and mid. No additional data structures are created that depend on the input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Wrong Binary Search Template

The Pitfall: Using while left < right with right = mid instead of the standard template.

# Alternative template (not recommended)
while left < right:
    mid = (left + right) >> 1
    if arr[mid] >= mid:
        right = mid
    else:
        left = mid + 1
return left if arr[left] == left else -1

The Solution: Use the standard template with while left <= right and first_true_index:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if arr[mid] >= mid:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index if first_true_index != -1 and arr[first_true_index] == first_true_index else -1

2. Returning Early When arr[mid] == mid

The Pitfall: Immediately returning mid when arr[mid] == mid is found.

# INCORRECT approach
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == mid:
        return mid  # Wrong! This might not be the smallest index

Why it's wrong: This fails to find the smallest index. For arr = [0, 1, 5, 8], if we check mid = 1 and find arr[1] == 1, we'd return 1, missing index 0.

The Solution: Always search left (right = mid - 1) when feasible to find the smallest index.

3. Forgetting the Final Validation

The Pitfall: Not checking if first_true_index is actually a fixed point.

# INCORRECT approach
return first_true_index  # Wrong! arr[first_true_index] might be > first_true_index

Why it's wrong: The feasible condition is arr[mid] >= mid, not arr[mid] == mid. The first feasible index might have arr[i] > i, not arr[i] == i.

The Solution: Always validate:

if first_true_index != -1 and arr[first_true_index] == first_true_index:
    return first_true_index
return -1

4. Integer Overflow in Mid Calculation

The Pitfall: Using mid = (left + right) / 2 could cause overflow in languages with fixed integer sizes.

The Solution: Use mid = left + (right - left) / 2. Python handles large integers gracefully, but this is good practice for portable code.