ADVERTISEMENT
ADVERTISEMENT

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

In this article, we will find how to search 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.
Submitted by Radib Kar, on February 03, 2021

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.

By Linear search

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

By Binary search

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++ Implementation:

#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
ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.