Find a Fixed Point (Value equal to index) in a given array

Problem Statement

Given a sorted array of distinct integers, find a fixed point. A fixed point is an index i such that arr[i] = i.

Constraints:

• Array is sorted in ascending order
• All elements are distinct
• Return any fixed point if multiple exist, or -1 if none exists

Example:

• Input: arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]
• Output: 3
• Explanation: arr[3] = 3, so 3 is a fixed point

Example 2:

• Input: arr = [0, 2, 5, 8, 17]
• Output: 0
• Explanation: arr[0] = 0, so 0 is a fixed point

Example 3:

• Input: arr = [-10, -5, 3, 4, 7, 9]
• Output: -1
• Explanation: No index i where arr[i] = i

Approach 1: Brute Force (Linear Search)

Intuition

Check each index to see if the value at that index equals the index itself.

Algorithm

1. Traverse the array from index 0 to n-1
2. At each index i, check if arr[i] == i
3. If found, return i
4. If no fixed point found, return -1

public class Solution {
    public int findFixedPoint(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == i) {
                return i;
            }
        }
        return -1;
    }
}

Complexity Analysis

• Time Complexity: O(n) - May need to check all elements
• Space Complexity: O(1) - No extra space used

Approach 2: Binary Search (Optimal)

Intuition

Since the array is sorted and contains distinct elements, we can use binary search. The key insight is:

• If arr[mid] < mid, the fixed point (if exists) must be on the right side
• If arr[mid] > mid, the fixed point (if exists) must be on the left side
• If arr[mid] == mid, we found a fixed point

Why this works:

• Array is sorted with distinct elements
• If arr[mid] < mid, then arr[mid-1] < mid-1 (since elements are distinct and sorted)
• Similarly, all elements to the left will also be less than their indices
• So we can safely search the right half

Algorithm

1. Initialize left = 0 and right = n-1
2. While left <= right:
   • Calculate mid = left + (right - left) / 2
   • If arr[mid] == mid, return mid
   • If arr[mid] < mid, search right half (left = mid + 1)
   • If arr[mid] > mid, search left half (right = mid - 1)
3. Return -1 if no fixed point found

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

Dry Run Example

Complexity Analysis

• Time Complexity: O(log n) - Binary search
• Space Complexity: O(1) - Only using pointers

Variation: Find Leftmost Fixed Point

If multiple fixed points exist, find the smallest index.

public class Solution {
    public int findLeftmostFixedPoint(int[] arr) {
        int left = 0, right = arr.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == mid) {
                result = mid;
                right = mid - 1;  // Continue searching left
            } else if (arr[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

Handling Non-Distinct Elements

When elements are not distinct, binary search needs modification since we can't simply discard half the array.

Key Takeaways

1. Binary Search Application: This is a classic application of binary search on a sorted array with distinct elements
2. Key Insight: The sorted and distinct properties allow us to eliminate half the search space
3. Comparison with Index: Instead of comparing with a target, we compare arr[mid] with mid
4. Non-Distinct Case: Requires a different approach as we can't always eliminate half the array
5. Multiple Fixed Points: Modify binary search to find leftmost/rightmost if needed
6. Edge Cases: Handle empty arrays and arrays with all negative or all positive numbers