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

Last Updated : 03 Jul, 2023

Given an array of n distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. Note that integers in array can be negative.
Examples:

  Input: arr[] = {-10, -5, 0, 3, 7}
  Output: 3  // arr[3] == 3 

  Input: arr[] = {0, 2, 5, 8, 17}
  Output: 0  // arr[0] == 0 


  Input: arr[] = {-10, -5, 3, 4, 7, 9}
  Output: -1  // No Fixed Point

Method 1 (Linear Search)
Linearly search for an index i such that arr[i] == i. Return the first such index found. Thanks to pm for suggesting this solution.

C++

// C++ program to check fixed point 
// in an array using linear search 
#include <bits/stdc++.h> 
using namespace std; 
  
int linearSearch(int arr[], int n) 
{ 
    int i; 
    for (i = 0; i < n; i++) { 
        if (arr[i] == i) 
            return i; 
    } 
  
    /* If no fixed point present then return -1 */
    return -1; 
} 
  
/* Driver code */
int main() 
{ 
    int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Fixed Point is " << linearSearch(arr, n); 
    return 0; 
} 
  
// This is code is contributed by rathbhupendra 

C

// C program to check fixed point 
// in an array using linear search 
#include <stdio.h> 
  
int linearSearch(int arr[], int n) 
{ 
    int i; 
    for (i = 0; i < n; i++) { 
        if (arr[i] == i) 
            return i; 
    } 
  
    /* If no fixed point present then return -1 */
    return -1; 
} 
  
/* Driver program to check above functions */
int main() 
{ 
    int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printf("Fixed Point is %d", linearSearch(arr, n)); 
    getchar(); 
    return 0; 
} 

Java

// Java program to check fixed point 
// in an array using linear search 
  
class Main { 
    static int linearSearch(int arr[], int n) 
    { 
        int i; 
        for (i = 0; i < n; i++) { 
            if (arr[i] == i) 
                return i; 
        } 
  
        /* If no fixed point present  
           then return -1 */
        return -1; 
    } 
    // main function 
    public static void main(String args[]) 
    { 
        int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
        int n = arr.length; 
        System.out.println("Fixed Point is "
                           + linearSearch(arr, n)); 
    } 
} 

Python3

# Python program to check fixed point  
# in an array using linear search 
def linearSearch(arr, n): 
    for i in range(n): 
        if arr[i] is i: 
            return i 
    # If no fixed point present then return -1 
    return -1
  
# Driver program to check above functions 
arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100] 
n = len(arr) 
print("Fixed Point is " + str(linearSearch(arr, n))) 
  
# This code is contributed by Pratik Chhajer 

C#

// C# program to check fixed point 
// in an array using linear search 
using System; 
  
class GFG { 
    static int linearSearch(int[] arr, int n) 
    { 
        int i; 
        for (i = 0; i < n; i++) { 
            if (arr[i] == i) 
                return i; 
        } 
  
        /* If no fixed point present  
        then return -1 */
        return -1; 
    } 
    // Driver code 
    public static void Main() 
    { 
        int[] arr = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
        int n = arr.Length; 
        Console.Write("Fixed Point is " + linearSearch(arr, n)); 
    } 
} 
  
// This code is contributed by Sam007 

PHP

<?php 
// PHP program to check fixed point  
// in an array using linear search 
  
function linearSearch($arr, $n) 
{ 
    for($i = 0; $i < $n; $i++) 
    { 
        if($arr[$i] == $i) 
            return $i; 
    } 
  
    // If no fixed point present then 
    // return -1 
    return -1; 
} 
  
    // Driver Code 
    $arr = array(-10, -1, 0, 3, 10,  
                  11, 30, 50, 100); 
    $n = count($arr); 
    echo "Fixed Point is ". 
            linearSearch($arr, $n); 
  
// This code is contributed by Sam007 
?> 

Javascript

<script> 
  
// JavaScript program to check fixed point  
// in an array using linear search  
  
    function linearSearch(arr, n) 
    { 
        let i; 
        for(i = 0; i < n; i++) 
        { 
            if(arr[i] == i) 
                return i; 
        } 
      
        /* If no fixed point present  
        then return -1 */
        return -1; 
    } 
  
// Driver Code 
    let arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]; 
    let n = arr.length; 
    document.write("Fixed Point is "
                + linearSearch(arr, n)); 
  
</script> 

Output:

Fixed Point is 3

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

Method 2 (Binary Search)
First check whether middle element is Fixed Point or not. If it is, then return it; otherwise if the index of middle + 1 element is less than or equal to the value at the high index, then Fixed Point(s) might lie on the right side of the middle point (obviously only if there is a Fixed Point). Similarly, check if the index of middle – 1 element is greater than or equal to the value at the low index, then Fixed Point(s) might lie on the left side of the middle point.

C++

// C++ program to check fixed point 
// in an array using binary search 
#include <bits/stdc++.h> 
using namespace std; 
  
int binarySearch(int arr[], int low, int high) 
{ 
    if (high >= low) { 
        int mid = low + (high - low) / 2; 
        if (mid == arr[mid]) 
            return mid; 
        int res = -1; 
        if (mid + 1 <= arr[high]) 
            res = binarySearch(arr, (mid + 1), high); 
        if (res != -1) 
            return res; 
        if (mid - 1 >= arr[low]) 
            return binarySearch(arr, low, (mid - 1)); 
    } 
  
    /* Return -1 if there is no Fixed Point */
    return -1; 
} 
  
/* Driver code */
int main() 
{ 
    int arr[10] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Fixed Point is " << binarySearch(arr, 0, n - 1); 
    return 0; 
} 
// This code is contributed by Ashutosh Singh 

C

// C program to check fixed point 
// in an array using binary search 
#include <stdio.h> 
  
int binarySearch(int arr[], int low, int high) 
{ 
    if (high >= low) { 
        int mid = low + (high - low) / 2; 
        if (mid == arr[mid]) 
            return mid; 
        int res = -1; 
        if (mid + 1 <= arr[high]) 
            res = binarySearch(arr, (mid + 1), high); 
        if (res != -1) 
            return res; 
        if (mid - 1 >= arr[low]) 
            return binarySearch(arr, low, (mid - 1)); 
    } 
  
    /* Return -1 if there is no Fixed Point */
    return -1; 
} 
  
/* Driver program to check above functions */
int main() 
{ 
    int arr[10] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printf("Fixed Point is %d", binarySearch(arr, 0, n - 1)); 
    getchar(); 
    return 0; 
} 

Java

// Java program to check fixed point 
// in an array using binary search 
  
class Main { 
  
    static int binarySearch(int arr[], int low, int high) 
    { 
        if (high >= low) { 
            int mid = low + (high - low) / 2; 
            if (mid == arr[mid]) 
                return mid; 
            int res = -1; 
            if (mid + 1 <= arr[high]) 
                res = binarySearch(arr, (mid + 1), high); 
            if (res != -1) 
                return res; 
            if (mid - 1 >= arr[low]) 
                return binarySearch(arr, low, (mid - 1)); 
        } 
  
        /* Return -1 if there is no Fixed Point */
        return -1; 
    } 
  
    // main function 
    public static void main(String args[]) 
    { 
        int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
        int n = arr.length; 
        System.out.println("Fixed Point is "
                           + binarySearch(arr, 0, n - 1)); 
    } 
} 

Python3

# Python program to check fixed point  
# in an array using binary search 
def binarySearch(arr, low, high): 
    if high >= low : 
          
        mid = low + (high - low)//2
        if mid == arr[mid]:  
            return mid 
        res = -1
        if mid + 1 <= arr[high]: 
            res = binarySearch(arr, (mid + 1), high) 
        if res !=-1: 
            return res 
        if mid-1 >= arr[low]: 
            return binarySearch(arr, low, (mid -1)) 
      
  
    # Return -1 if there is no Fixed Point 
    return -1
  
  
  
  
# Driver program to check above functions */ 
arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100] 
n = len(arr) 
print("Fixed Point is " + str(binarySearch(arr, 0, n-1))) 

C#

// C# program to check fixed point 
// in an array using binary search 
using System; 
  
class GFG { 
  
    static int binarySearch(int[] arr, int low, int high) 
    { 
        if (high >= low) { 
            int mid = low + (high - low) / 2; 
            if (mid == arr[mid]) 
                return mid; 
            int res = -1; 
            if (mid + 1 <= arr[high]) 
                res = binarySearch(arr, (mid + 1), high); 
            if (res != -1) 
                return res; 
            if (mid - 1 >= arr[low]) 
                return binarySearch(arr, low, (mid - 1)); 
        } 
  
        /* Return -1 if there is no Fixed Point */
        return -1; 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        int[] arr = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; 
        int n = arr.Length; 
        Console.Write("Fixed Point is " + binarySearch(arr, 0, n - 1)); 
    } 
} 

PHP

<?php 
// PHP program to check fixed point 
// in an array using binary search 
  
  
function binarySearch($arr, $low, $high) 
{ 
    if($high >= $low) 
     { 
       $mid = (int)($low + ($high - $low)/2);  
       if($mid == $arr[$mid]) 
      return $mid; 
       $res = -1; 
       if($mid+1 <= $arr[$high]) 
      $res = binarySearch($arr, ($mid + 1), $high); 
       if($res!=-1) 
          return $res; 
       if($mid-1 >= $arr[$low]) 
      return binarySearch($arr, $low, ($mid -1)); 
     } 
  
     /* Return -1 if there is no Fixed Point */
     return -1; 
} 
  
  
  
    // Driver Code 
    $arr = array(-10, -1, 0, 3, 10, 
                  11, 30, 50, 100); 
    $n = count($arr); 
    echo "Fixed Point is: " 
        . binarySearch($arr, 0, $n - 1); 
          
?> 

Javascript

<script> 
  
// javascript program to check fixed point  
// in an array using binary search   
  
  
  
function binarySearch(arr,low,high) 
{ 
    if(high >= low) 
     { 
       let mid = math.floor(low + (high - low)/2);  
       if(mid == arr[mid]) 
      return mid; 
       let res = -1; 
       if(mid+1 <= arr[high]) 
      res = binarySearch(arr, (mid + 1), high); 
       if(res!=-1) 
          return res; 
       if(mid-1 >= arr[low]) 
      return binarySearch(arr, low, (mid -1)); 
     } 
  
     /* Return -1 if there is no Fixed Point */
     return -1; 
} 
  
  
  
    // Driver program  
    let arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100];  
    let n = arr.length;  
    document.write("Fixed Point is "+ binarySearch(arr, 0, n-1));  
      
</script> 

Output:

Fixed Point is 3

Algorithmic Paradigm: Divide & Conquer

Time Complexity: O(log n)

Auxiliary Space: O(log n) (As implicit stack is used for recursive calls)

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

GeeksforGeeks

Improve

Previous Article

Find the Minimum element in a Sorted and Rotated Array

Find the k most frequent words from a file

Similar Reads

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

Given an array of n integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in the array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. Note that integers in the array can be negative. Examples: Input: arr[] = {-10, -5, 0, 3, 7} Output

Maximum Fixed Point (Value equal to index) in a given Array

Given an array arr[] of size N, the task is to find the maximum index i such that arr[i] is equal to i. If there is no such index in the array arr[] then print -1. Examples: Input: arr[ ] = {-10, -5, 0, 3, 7}Output: 3Explanation: Only for i=3, arr[3] = 3 Input: arr[ ] = {0, 2, 5, 8, 4}Output: 4 Approach: Follow the steps below to solve this problem

Minimum index i such that all the elements from index i to given index are equal

Given an array arr[] of integers and an integer pos, the task is to find the minimum index i such that all the elements from index i to index pos are equal. Examples: Input: arr[] = {2, 1, 1, 1, 5, 2}, pos = 3 Output: 1 Elements in index range [1, 3] are all equal to 1. Input: arr[] = {2, 1, 1, 1, 5, 2}, pos = 5 Output: 5 Brute Force Approach: A br

Count pairs in given Array having sum of index and value at that index equal

Given an array arr[] containing positive integers, count the total number of pairs for which arr[i]+i = arr[j]+j such that 0≤i<j≤n-1. Examples: Input: arr[] = { 6, 1, 4, 3 }Output: 3Explanation: The elements at index 0, 2, 3 has same value of a[i]+i as all sum to 6 {(6+0), (4+2), (3+3)}. Input: arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 }Output: 28 Naive

Find a Fixed Point in an array with duplicates allowed

Given an array of n duplicates or distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in the array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. Note that integers in the array can be negative. Examples : Input : arr[] =

Find maximum difference between elements having a fixed index difference of K

Given an integer K and an unsorted array of integers arr[], find the maximum difference between elements in the array having a fixed index difference of K. Examples: Input: arr[] = [2, 9, 7, 4, 6, 8, 3], K = 2Output: 5Explanation: The maximum absolute difference with an index difference of two is 5, which occurs between arr[0] and arr[2] Input: arr

Find time required to reach point N from point 0 according to given rules

Given two positive integers X and Y and N number of points arranged in a line, the task is to find the time required to reach point N from point 0 according to the following rules: Every point has one barrier that closes after every Y minutes and remains closed for the next Y minutes.On reaching a point if the barrier is closed, then the person nee

Check if digit cube limit of an integer arrives at fixed point or a limit cycle

Given an integer N, the task is to check if the Digit Cube limit of an integer arrives at a fixed point or in a limit cycle. A Digit Cube Limit is a number which repeatedly arrives at a point if its value is computed as the sum of cubes of its digits, i.e. they have the following properties: Arrive at a fixed point if it is an Armstrong number.Arri

Check if it is possible to reach to the index with value K when start index is given

Given an array arr[] of N positive integers and two positive integers S and K, the task is to reach the position of the array whose value is K from index S. We can only move from current index i to index (i + arr[i]) or (i – arr[i]). If there is a way to reach the position of the array whose value is K then print "Yes" else print "No". Examples: In

Farthest index that can be reached from the Kth index of given array by given operations

Given an array arr[] consisting of N integers and three integers X, Y, and K, the task is to find the farthest index that can be reached by the following operations: If arr[i] ? arr[i + 1]: Move from index i to i + 1.If arr[i] < arr[i+1]: Either decrement X by 1 if the value of X > 0 or decrement Y by (arr[i + 1] - arr[i]) if the value of Y

Article Tags :

Practice Tags :