Fixed Point

Updated on 29 May, 2025
Fixed Point header image

Problem Statement

In this task, you are provided with a sorted array of unique integers named arr. The array is sorted in ascending order. Your objective is to find the smallest index i for which the value of the element at that index equals the index itself (arr[i] == i). If no such index exists, the function should return -1. This problem not only tests basic array manipulation but also checks for optimal approaches to searching in a sorted structure.

Examples

Example 1

Input:

arr = [-10,-5,0,3,7]

Output:

3

Explanation:

For the given array, `arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3`, thus the output is 3.

Example 2

Input:

arr = [0,2,5,8,17]

Output:

0

Explanation:

`arr[0] = 0`, thus the output is 0.

Example 3

Input:

arr = [-10,-5,3,4,7,9]

Output:

-1

Explanation:

There is no such `i` that `arr[i] == i`, thus the output is -1.

Constraints

  • 1 <= arr.length < 104
  • -109 <= arr[i] <= 109

Approach and Intuition

When approaching the problem where an array is sorted, a binary search methodology becomes an appealing option since it can help reduce the search space significantly. Let's discuss the intuition with reference to the examples provided:

  • Example 1: Here the array is [-10, -5, 0, 3, 7]. A simple iteration from the start would eventually get us to the point where the index 3 contains the value 3 (arr[3] == 3). This situation is straightforward because the binary search will efficiently find this point since we continuously narrow our search to where arr[i] can potentially be equal to i.

  • Example 2: This example comprises a first element where the index and the value are the same (arr[0] = 0). This case highlights a scenario that can be quickly identified even in the first check of our binary search process.

  • Example 3: This situation with [-10, -5, 3, 4, 7, 9] demonstrates the case where no index satisfies the condition. The smart application of binary search allows us to discern that there is no solution faster than comparing each element sequentially.

Steps Employed in Binary Search Approach:

  1. Set initial boundary conditions: left to 0 and right to len(arr) - 1.
  2. Loop while left is less than or equal to right:
    • Calculate the middle index: mid = (left + right) // 2.
    • If arr[mid] == mid, then this might be our answer, but we continue searching to the left to find a potentially smaller index that also satisfies the condition.
    • If arr[mid] < mid, then any potential arr[i] == i must be to the right, so set left to mid + 1.
    • Conversely, if arr[mid] > mid, we check to the left by setting right to mid - 1.
  3. If we exit the loop without finding any such index, return -1.

Using this method allows us to optimize our search process down to a log-scaled time complexity, leveraging the sorted nature of the array.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    int findFixedPoint(vector<int>& data) {
        int start = 0, end = data.size() - 1;
        int result = -1;
        
        while (start <= end) {
            int middle = start + (end - start) / 2;
            
            if (data[middle] == middle) {
                result = middle;
                end = middle - 1;
            } else if (data[middle] < middle) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
        
        return result;
    }
};

The solution provided implements a method to find a "fixed point" in an array using the binary search algorithm. A fixed point in an array is an index i such that data[i] is equal to i.

  • Initialize start to 0 and end to the last index of data.
  • Initialize result to -1 to represent the absence of a fixed point initially.
  • Use a while loop to conduct the binary search as long as start is less than or equal to end:
    • Calculate the middle index middle.
    • Check if the element at this middle index is the same as its index. If true, store this index in result and narrow the search to the left half to find the smallest fixed point (if any).
    • If the middle element is less than its index, move the start index to middle + 1, shifting the search range to the right.
    • If the middle element is greater than its index, update the end index to middle - 1, focusing the search on the left part.
  • At the end of the loop, return result. If a fixed point exists, result will contain the smallest index that satisfies the fixed point condition. Otherwise, it will return -1, indicating no fixed point was found.

This implementation efficiently finds and confirms the presence of a fixed point using binary search, making it optimal for sorted arrays, ensuring a time complexity of O(log n), where n is the number of elements in the array.

java
class Solution {
    public int searchFixedPoint(int[] data) {
        int lo = 0, hi = data.length - 1;
        int result = -1;
        
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            
            if (data[mid] == mid) {
                result = mid;
                hi = mid - 1; // Shift search area to left
            } else if (data[mid] < mid) {
                lo = mid + 1; // Search in right half
            } else {
                hi = mid - 1; // Search in left half
            }
        }
        
        return result;
    }
}

The provided Java code implements a method to find a fixed point in an array. A fixed point is an index where the element at that index is equal to the index itself, e.g., data[i] == i.

The method named searchFixedPoint employs a binary search algorithm to efficiently locate the fixed point. Here’s how it functions:

  1. Initialize two pointers, lo and hi, representing the start and end of the array segment being searched.
  2. Initiate a loop that continues as long as lo is less than or equal to hi.
  3. Calculate the midpoint of the current segment using (lo + hi) / 2. This position is continuously updated based on the results of each comparison.
  4. If the element at this midpoint position equals the midpoint (i.e., data[mid] == mid), then:
    • Assign this position as the result.
    • Adjust hi to search the left side of the array for any earlier fixed point occurrence.
  5. If the element at the midpoint is less than the midpoint (data[mid] < mid), move the lo pointer to mid + 1 to search the right half of the array segments.
  6. If the element at the midpoint is greater than the midpoint, adjust the hi pointer to mid - 1 to search the left half.

The method returns the first occurrence of the fixed point if it exists, returning -1 if no fixed point is found. This return value effectively indicates that no index in the array satisfies the condition data[index] == index.

This approach ensures a time complexity of O(log n) due to the binary search technique, making it efficient for large datasets.

python
class Solution:
    def findFixedPoint(self, values: List[int]) -> int:
        start, end = 0, len(values) - 1
        result = -1

        while start <= end:
            middle = (start + end) // 2

            if values[middle] == middle:
                result = middle
                end = middle - 1
            elif values[middle] < middle:
                start = middle + 1
            else:
                end = middle - 1

        return result

Discover the method to identify a fixed point in an array where the element's value equals its index, using Python. The provided code implements a binary search technique to efficiently locate such a position within a sorted list of integers.

  • The function findFixedPoint initializes two pointers, start and end, to represent the range currently being searched.
  • A variable result is initialized to -1, to store the result if a fixed point is found.
  • A while loop continues until start exceeds end. Inside this loop:
    • Calculate the midpoint of the current range.
    • If the element at the midpoint index is equal to the index itself, update result with this index and narrow the search to the left half to possibly find a lower fixed point.
    • If the element is less than the midpoint index, adjust the start pointer to focus on the right half; otherwise, adjust the end pointer to focus on the left half.
  • The process concludes by returning result, which will either be -1 (indicating no fixed point was found) or the index of a fixed point, with preference given to the lowest fixed point if multiple are present.

Implement this solution to determine the fixed point in your data, ensuring efficient performance even with sizable input arrays.

Comments

No comments yet.