• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

August 12, 2014 by Dhaval Dave

Given an array of n distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array such that Arr[i] = i .
If there is any Fixed Point present in array, else returns -1.
Note that integers in array can be negative.

Example :

  Input: arr[] = {-2, -1, 1, 3, 5}
Output: 3 // arr[3] == 3

Input: arr[] = {-4, -1, 1, 2, 5, 8}
Output: -1 // No Fixed Point

First Simple Method : Linear Search
for(i = 0; i < n; i++){
        if(arr[i] == i) return i;
}
Complexity O(n)

Method 2 : Divide and Conquer (As numbers is sorted we can use it as binary search)

Thanks to Dhaval for suggesting this Code.

int indexSearch(int arr[], int low, int high)
{
    if(high >= low)
    {
        int mid = (low + high)/2;
        if(mid == arr[mid])
            return mid;
        if(mid > arr[mid])
            return indexSearch(arr, (mid + 1), high);
        else
            return indexSearch(arr, low, (mid -1));
    }

    /* Return -1 if there is no Fixed Point */
    return -1;
}
int main()
{
    int arr[] = {-2, -1, 1, 3, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf(“Fixed Point is %d”, indexSearch(arr, 0, n-1));
    getchar();
    return 0;
}

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Hacker Earth Questions, Interview Questions, problem Tagged With: Array

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

SAP Off Campus Hiring_ March 2015 Verbal Skills

Hackerearth : Counting Subarrays

Mirror of Tree

Stock Buy Sell to Maximize Profit

Find and print longest consecutive number sequence in a given sequence in O(n)

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

Client Server C program

Fibonacci Hashing & Fastest Hashtable

Right view of Binary tree

Check Binary Tree is Binary Search Tree or not

C Program for TAIL command of UNIX

Find Percentage of Words matching in Two Strings

SAP Off Campus Hiring_ March 2015 Computer Skills

Find Nearest Minimum number in left side in O(n)

Flipkart Set 1 On Campus with Answers

Serialise Deserialise N-ary Tree

Find the element that appears once others appears thrice

Password Predictor

Generic Object Oriented Stack with Template

The greedy coins game Dynamic Programming

Python Array String

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

FizzBuzz Solution C C++

Daughter’s Age VeryGood Puzzle

Leetcode: Edit Distance

Wrong Directions given find minimum moves so that he can reach to the destination

Difference between a LinkedList and a Binary Search Tree BST

Find min element in Sorted Rotated Array (With Duplicates)

Closed Parentheses checker

Copyright © 2025 · Genesis Framework · WordPress · Log in