Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Linear Search
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity Analysis
3.2.2.
Space Complexity Analysis
4.
Binary Search
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Time Complexity Analysis 
4.2.2.
Space Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is the value of the index for the first element?
5.2.
What is the asymptotic complexity of finding an array element based on index?
5.3.
Why does indexing an array take O(1) time?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

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

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Finding a Fixed Point whose value is equal to the index in a given array. It is a well-known practice problem for learning problem-solving and time complexity optimization; various interview panels had also asked it for the roles of SDE intern. 

In this article, we’ll use two methods to solve this problem; the first is the brute force, the Linear search, and using Binary Search.

Problem Statement

Given a sorted array of n distinct integers, write a function that returns a Fixed Point in the array whose value is equal to the index, else returns -1.

Find the element whose arr[ndex]=index.

Sample Examples

Example 1

Input

Enter size of array: 4

Enter array = {7,1,3,2}

Output

Fixed Point: 1

Explanation

Element 1 will be the output whose value and index both are the same, which is 1.\

 

Example 2

Input

Enter size of array: 5

Enter array = {1,6,9,4,10}

Output

No fixed point in the array

Explanation

As none of the elements are found whose value and index are the same, we will print “No fixed point in the array”.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}


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 AnalysisSorting Based ProblemsNumber Theory, and Dynamic Programing to learn.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive 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!

Previous article
Find the minimum element in a sorted and Rotated Array
Next article
Plates Between Candles
Live masterclass