Find a fixed point in a given array

Difficulty: Easy , Asked-In: Amazon, Hike

Key takeaway: An excellent problem beginners to learn problem solving using binary search.

Let’s understand the problem

Write a program that returns the index of a fixed point in the given sorted array of distinct integers. A fixed point is an index i such that X[i] is equal to i. If a fixed point is found, we should return its index. If no fixed point is found, we should return -1. Note that the integers in the array may be both positive and negative.

Examples

Input: X[] = [-4, -2, 0, 1, 4, 6, 7], Output: 4

Explanation: X[4] == 4.

Input: X[] = [-10, -5, 3, 4, 7, 9], Output: -1

Explanation: There is no such fixed point in the array.

Discussed solution approaches

Brute force approach using the linear search
Efficient approach using binary search

Brute force approach using the linear search

One basic approach to finding a fixed point is to linearly search the array for an index i such that X[i] == i and return the first such index found. This approach has a time complexity of O(n). However, we can improve the time complexity by utilizing the sorted nature of the array and the properties of fixed points. Can we find a way to do this? Think!

int getFixedPoint(int X[], int n)  
{  
    for(int i = 0; i < n; i = i + 1)  
    {  
        if(X[i] == i)  
            return i;
    }  
    return -1;
}

Efficient approach Using binary search

Solution idea using recursive binary search

To find the fixed point, we can use a binary search approach. First, we calculate the middle index mid and check if mid is equal to X[mid]. If it is, we return mid as the fixed point. If mid is greater than X[mid], there may be one or more fixed points on the right side of mid. To search for these fixed points, we recursively call the same function with the indices of the right subarray.

On the other hand, if mid is less than X[mid], there may be one or more fixed points on the left side of mid. To search for these fixed points, we recursively call the same function with the indices of the left subarray. If the left index becomes greater than the right index, we return -1, indicating that no fixed point was found.

Solution code C++

int getFixedPoint(int X[], int l, int r) 
{
    if (r >= l) 
    {
        int mid = (l + r) / 2;
        if (mid == X[mid])
            return mid;
        if (mid > X[mid])
            return getFixedPoint(X, mid + 1, r);
        else
            return getFixedPoint(X, l, mid - 1);
    }
    
    return -1;
}

Solution idea using iterative binary search binary search

We calculate the middle index, mid, and check if mid is equal to X[mid]. If it is, we return "mid" as the fixed point. If "mid" is not a fixed point, we determine which half of the search space (left or right) may contain the fixed point and update the loop variable accordingly. During the iteration, if the left index becomes greater than the right index, we return -1, indicating that no fixed point was found.

Solution code C++

int getFixedPoint(int X[], int l, int r) 
{
    while (l <= r) 
    {
        int mid = (l + r) / 2;
        if (mid == X[mid])
            return mid;
        if (mid > X[mid])
            l = mid + 1;
        else
            r = mid - 1;
    }
    
    return -1;
}

Solution analysis

At each step of recursion or iteration, we reduce the search space by half. As a result, the time complexity of both implementations is equal to the time complexity of binary search, which is O(log n).

The space complexity of the recursive implementation is equal to the size of the recursion call stack, which is equal to the height of the recursion tree. As the input size is halved after each recursive call, the height of the recursion tree will be O(log n). Therefore, the space complexity of the recursive implementation is O(log n). In the iterative implementation, we use constant extra space, so the space complexity of the iterative implementation is O(1).

Critical ideas to think: How can we modify the above approach if there are repeated values in the sorted array?