Find a Fixed Point (Value equal to Index) in a Given Array

Linear Search

We will traverse the array from start to end and check the condition for the fixed point; if the condition is true, we print the element; otherwise, we print "No fixed point in the array."

Algorithm

1. For each element, until the end of the array.
2. Determine whether the element value and the index value are the same. If this is the case, print the element.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cout<<"Enter size of array:";
    cin>>N;
    int arr[N];
    cout<<"Enter array = ";
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    for(int i = 0; i < N; i++)
    {
        if(arr[i] == i)
        {
            cout<<"Fixed Point: " <<index<<endl;
            return 0;
        }
    }
    cout<<"No fixed point in the array \n";
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter size of array: 4
Enter array = {7,1,3,2}

Output

Fixed Point: 1

Time Complexity Analysis

O(n), where n is the size of the array. We only traverse the array once, resulting in linear time complexity.

Space Complexity Analysis

Because we don't use auxiliary space, the space complexity is O(1).

Check out this problem - First And Last Occurrences Of X

Binary Search

"How do we improve time complexity?" is now the critical question. Can we reduce the time complexity of searching because it is the most important operation in the problem? Let's give it some thought!

In this case, we can apply this method to the sorted array. Use a binary search to determine the condition for a fixed point. Print that element if such a position is found; otherwise, print "No fixed point in the array."

Algorithm

1. Assign the low and high variables to the beginning and end of the array, respectively.
2. Until low is less than high- First, determine whether the middle element is a fixed point and print the middle element.
   1. The condition is met if the mid element value is less than the mid index. If so, update from low to mid +1.
   2. If the mid element value exceeds the mid index. If so, update the high to mid -1.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int bin_search(int arr[],int l , int h)
{
    if(l <= h)
    {
        // getting the mid element
        int mid = l + (h - l)/2;
        if(arr[mid] == mid)
        return mid;
  
        int res = -1;
        //recursively calling the function to get element
        if (mid < arr[h])
            res = bin_search(arr, (mid + 1), h);
        if (res != -1)
            return res;
        if (mid - 1 >= arr[l])
            return bin_search(arr, l, (mid - 1));
        }
    return -1;
}

int main()
{
    int n;
    cout<<"Enter size of array:";
    cin>>n;
    int arr[n];
    cout<<"Enter array = ";
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    // calling the function
    int index = bin_search(arr,0,n-1);
    if(index >=0)
        cout <<"Fixed Point: " <<index<<endl;
    else
        cout<<"No fixed point in the array \n";
    return 0;
}

Input

Enter size of array: 4
Enter array = {7,1,3,2}

Output

Fixed Point: 1

Time Complexity Analysis 

The time complexity of the above approach O(logN), where N is the array size. In this case, we use binary search, which has a logn time complexity.

Space Complexity Analysis

Because we don't use auxiliary space, the space complexity is O(1).

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

What is the value of the index for the first element?

The index value of the array's first element is 0.
 

What is the asymptotic complexity of finding an array element based on index?

It is constant O(1).
 

Why does indexing an array take O(1) time?

The first element, address location and the index requested, which is a pointer to memory and highly fast, is how arrays store items in contiguous memory. We discussed two approaches to solve this problem

Conclusion

This article extensively discussed the problem of Finding a Fixed Point whose value is equal to the index in a given array. We discussed two approaches to solve the problem and implemented both approaches in C++.

We hope this blog has helped you enhance your knowledge regarding searching in array problems. Are you interested in reading/exploring additional articles about this topic? Don't worry; Coding Ninjas has you covered. See Time Complexity and Analysis, Sorting Based Problems, Number Theory, and Dynamic Programing to learn.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, and many more! You can also check Interview Experiences and Interview Preparation Resources if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!