Home » Algorithms

Find a Fixed Point (Value equal to index) in a given array

Find fixed point in an array: In this tutorial, we will learn how to find a fixed point in a given sorted array of distinct elements using both linear search & binary search. If there is no fixed point, then return -1. By Radib Kar Last updated : August 10, 2023

Problem statement

Say, the given array is [-8, -1, 1, 3, 6, 12] then the fixed element is 3. If the given array is [-5, -1, 10] then there is no fixed point and thus return -1.

Using Linear Search: Find a fixed point (value equal to index) in an array

We can easily search this by linear search checking for the condition arr[index] ==index like below,

for (int i = 0; i < arr.size(); i++) {
    if (arr[i] == i) {
        fixedNumber = arr[i];
        break;
    }
}

Using Binary Search: Find a fixed point (value equal to index) in an array

We can use binary search also as the array is sorted. So, if arr[pivot] is < pivot then we need to move towards the right half, else if arr[pivot] is > pivot then we need to move towards the left half, otherwise, we found our fixed element.

Below is the implementation for that,

while (start <= end) {

    int mid = start + (end - start) / 2;
    if (arr[mid] == mid) {
        fixedNumber = arr[mid];
        break;
    }
    else if (arr[mid] < mid) {
        start = mid + 1;
    }
    else
        end = mid - 1;
}

C++ program to find a fixed point (value equal to index) in an array

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

//naive approach
void findFixedNumbereNaive(vector<int>& arr)
{
    cout << "..............Using naive search......\n";

    //O(n) time complexity

    int fixedNumber = -1;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == i) {
            fixedNumber = arr[i];
            break;
        }
    }
    if (fixedNumber == -1)
        cout << "There is no fixed number in this array\n";
    else
        cout << "The fixed number is " << fixedNumber << "\n";

    return;
}

void findFixedNumberEfficient(vector<int>& arr)
{

    cout << "..............Using efficient approach(binary search)......\n";

    //O(logn) time complexity

    int start = 0, end = arr.size() - 1;

    int fixedNumber = -1;

    while (start <= end) {

        int mid = start + (end - start) / 2;
        if (arr[mid] == mid) {
            fixedNumber = arr[mid];
            break;
        }
        else if (arr[mid] < mid) {
            start = mid + 1;
        }
        else
            end = mid - 1;
    }
    if (fixedNumber == -1)
        cout << "There is no fixed number in this array\n";
    else
        cout << "The fixed number is " << fixedNumber << "\n";

    return;
}

int main()
{
    cout << "Enter number of elements\n";
    int n;
    cin >> n;
    vector<int> arr(n);
    cout << "Enter the elements(sorted and distinct)\n";

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    //using navive approach
    findFixedNumbereNaive(arr);
    //using binary search
    findFixedNumberEfficient(arr);

    return 0;
}

Output

Enter number of elements
6
Enter the elements(sorted and distinct)
-8 -1 1 3 6 12
..............Using naive search......
The fixed number is 3
..............Using efficient approach(binary search)......
The fixed number is 3