Problem Description

You are given an array arr of distinct integers sorted in ascending order. Your task is to find the smallest index i where the value at that index equals the index itself (i.e., arr[i] == i). If no such index exists, return -1.

For example:

• If arr = [-10, -5, 0, 3, 7], the answer would be 3 because arr[3] = 3
• If arr = [0, 2, 5, 8, 17], the answer would be 0 because arr[0] = 0
• If arr = [-10, -5, 3, 4, 7, 9], the answer would be -1 because no index satisfies the condition

The solution uses binary search to efficiently find the answer. The key insight is that since the array is sorted and contains distinct integers:

• If arr[mid] >= mid, then the fixed point (if it exists) must be at index mid or to the left of mid
• If arr[mid] < mid, then the fixed point (if it exists) must be to the right of mid

This property allows us to eliminate half of the search space in each iteration, achieving O(log n) time complexity instead of the naive O(n) approach of checking every element.

Intuition

The key observation is that we're looking for a point where arr[i] = i. Let's think about what happens as we move through the array:

Since the array contains distinct integers in ascending order, when we examine any index mid:

• If arr[mid] = mid, we've found a fixed point
• If arr[mid] > mid, the value is "ahead" of its index
• If arr[mid] < mid, the value is "behind" its index

Here's the crucial insight: because the array is sorted and contains distinct integers, the difference arr[i] - i can only increase or stay the same as we move right (it can never decrease by more than 1 per step).

Why? As we move from index i to i+1:

• The index increases by exactly 1
• The array value increases by at least 1 (since values are distinct and sorted)
• Therefore, (arr[i+1] - (i+1)) >= (arr[i] - i)

This means if at some position mid we have arr[mid] < mid, then for all positions to the left of mid, we'll also have arr[j] < j. There's no way for a value to "catch up" to its index when moving left.

Similarly, if arr[mid] >= mid, there might be a fixed point at mid or to its left, but we need to check the leftmost such position to find the smallest index.

This monotonic property of arr[i] - i allows us to use binary search: we can safely eliminate half of the array in each step based on the comparison at the middle element, reducing our search from O(n) to O(log n).

Learn more about Binary Search patterns.

Solution Approach

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

We initialize two pointers:

• left = 0: starting from the beginning of the array
• right = len(arr) - 1: starting from the end of the array

The binary search loop continues while left < right:

1. Calculate the middle index: mid = (left + right) >> 1

   • The >> 1 operation is a bitwise right shift, equivalent to integer division by 2
   • This gives us the middle position between left and right

2. Check the condition at mid:

   • If arr[mid] >= mid: This means we might have found a fixed point at mid, or there could be one to the left. We set right = mid to search the left half (including mid itself since it could be the answer)
   • If arr[mid] < mid: This means there's no fixed point at mid or to its left. We set left = mid + 1 to search the right half

3. Why this works: The condition arr[mid] >= mid is the key. When this is true, we know:

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

4. Loop termination: When left == right, we've narrowed down to a single candidate position

5. Final check: After the loop, we check if arr[left] == left:

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

The algorithm guarantees finding the smallest index because we always move right to mid when a potential solution exists, ensuring we explore all smaller indices before settling on an answer.

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
• Array visualization with indices:

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

Iteration 1:

• mid = (0 + 4) >> 1 = 2
• Check arr[2] = 0 vs mid = 2
• Since 0 < 2, we have arr[mid] < mid
• This means no fixed point exists at index 2 or to its left
• Update: left = mid + 1 = 3

Iteration 2:

• left = 3, right = 4
• mid = (3 + 4) >> 1 = 3
• Check arr[3] = 3 vs mid = 3
• Since 3 >= 3, we have arr[mid] >= mid
• This means a fixed point might exist at index 3 or to its left
• Update: right = mid = 3

Iteration 3:

• left = 3, right = 3
• Loop terminates since left == right

Final Check:

• Check if arr[3] == 3
• Yes! arr[3] = 3
• 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 checked if anything smaller exists

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.

Solution Implementation

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. Incorrect Boundary Update When arr[mid] == mid

The Pitfall: A common mistake is to immediately return mid when arr[mid] == mid is found, thinking we've found the answer.

# INCORRECT approach
while left < right:
    mid = (left + right) >> 1
    if arr[mid] == mid:
        return mid  # Wrong! This might not be the smallest index
    elif arr[mid] > mid:
        right = mid - 1
    else:
        left = mid + 1

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

The Solution: Continue searching the left half even when finding a match to ensure we get the smallest index:

if arr[mid] >= mid:  # Include the equality case
    right = mid      # Keep mid as a candidate, search left

2. Off-by-One Error in Boundary Updates

The Pitfall: Setting right = mid - 1 when arr[mid] >= mid, which could skip over the actual answer.

# INCORRECT approach
if arr[mid] >= mid:
    right = mid - 1  # Wrong! Could miss the answer at index mid

Why it's wrong: If arr[mid] == mid and this is the smallest such index, setting right = mid - 1 would exclude it from our search space.

The Solution: Keep right = mid to include the current position in the next search iteration when it could be a valid answer.

3. Forgetting the Final Validation

The Pitfall: Returning left directly without checking if it's actually a fixed point.

# INCORRECT approach
while left < right:
    # ... binary search logic
  
return left  # Wrong! left might not satisfy arr[left] == left

Why it's wrong: The binary search narrows down to a candidate position, but doesn't guarantee that position is a fixed point. For example, with arr = [1, 2, 3], the search would end at left = 0, but arr[0] = 1 ≠ 0.

The Solution: Always validate the final position:

return left if arr[left] == left else -1

4. Integer Overflow in Mid Calculation (Less Common in Python)

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

The Solution: Use mid = left + (right - left) // 2 or bit shift mid = (left + right) >> 1. While Python handles large integers gracefully, this is good practice for writing portable code.