Searching: Find fixed point in the given array

Problem Statement:

You are given an array.

You need to find the fixed point.

A fixed point is a value equal to index.

If there is no fixed point, then return -1.

Example:

Input: arr[] = [-12, -10, 0, 3, 7]
Output: 3  

The value at index 3 is equal to 3

Solution 1: Brute force approach

Iterate through the array and find the index of the first index point.

Time Complexity: O(1)
Space Complexity: O(1)

Solution 2: Binary search approach

Use binary search to find the index of the fixed point.

we use the mid element to get the fixed point.

Below are the conditions for binary search:

if min == arr[mid]; return mid index

if mid > arr[mid]; move start = mid+1

if mid < arr[mid]; move end = mid -1

If start > end, return -1

Time Complexity: O(logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;


int solution_1 (vector<int> &arr) 
{
    for (int i = 0; i < arr.size(); i++) 
    {
        if (arr[i] == i)
            return i;
    }

    return -1;
}

int solution_2 (vector<int> &arr) 
{

    int low = 0, high = arr.size() - 1;

    while (low <= high) 
    {
        int mid = low + (high - low) / 2;

        if (arr[mid] == mid)
            return mid;
        else if (arr[mid] < mid)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

int main() 
{
    vector<int> arr = { -12, -10, 0, 3, 7 };
    cout<<solution_1 (arr)<<endl;
    cout<<solution_2(arr);
    return 0;
}

Output

3
3