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.
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
Use bin search
ReplyDelete1.if mid value mid then search in left part.
3.return mid if found else -1.