### Find Fixed Point (x[i]=i) in an Array

**Source:**Asked in an Amazon interview to a friend

**Problem:**

Given an array of size

*n*,

*x[0 .. n-1]*of integers sorted into ascending order with no duplicates, find an array item that is also its index, so that

*x[i] = i*.

For example,

*x[3] = 3*in the array shown below:

*i 0 1 2 3 4 5*

*x[i] -3 0 1 3 5 7*

Your task is to write a program that finds

*i*.

**Disclaimer:**

Yes, its a very easy problem, as far as algorithm is concerned. Its here for people preparing for interviews to see if they can write code.

Binary search or better?

ReplyDeleteOnce you know that f(i) = x[i]-i is an non-decreasing sequence, it's a simple binary search

ReplyDeleteBinary search!!

ReplyDeleteIf x[i] == i, return

if x[i] < i, move right

if x[i] > i, move left

[x for i,x in enumerate(a) if i==x][0]

ReplyDeleteDo binary search. Will take O(log n)

ReplyDeleteint FixedPointBinarySearch(int a[],int n)

ReplyDelete{

int mid=(n)/2;

if(n==1)

return 0;

if(a[mid]==mid)

return mid;

else if(a[mid]<mid)

return mid+FixedPointBinarySearch(a+mid+1,n-mid-1);

else

return FixedPointBinarySearch(a,n-mid);

}

idx = 0

ReplyDeletefor spread = 0 to max_number(array)

if spread = idx then msgbox "match"

idx = idx + 1

next spread

could add segment if multiples;

public int findI(int[] a){

ReplyDeleteint n = a.length;

if(a[0]>n || a[n-1]<0){

return -1;

}

int temp = n/2;

while(true){

if(temp > n-1)

return -1;

if(a[temp]==temp)

return temp;

else if(a[temp]>temp)

temp = temp/2;

else

temp = temp + temp/2;

}

}

return i if found and -1 otherwise!!!

def fixpoint(a):

ReplyDeletex,y = 0,len(a)

while x+1 != y:

h = x + ((y - x) >> 1)

if a[h] <= h:

x = h

else:

y = h

return a[x] == x