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