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
 For each element, until the end of the array.
 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
 Assign the low and high variables to the beginning and end of the array, respectively.

Until low is less than high First, determine whether the middle element is a fixed point and print the middle element.
 The condition is met if the mid element value is less than the mid index. If so, update from low to mid +1.
 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,n1);
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 
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 Productbased companies like Amazon, Microsoft, Uber, etc.
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!