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.
Solution:
Highlight the part between the * symbols for the answer.
* Binary search in O(log n). Because the array is sorted with no duplicates, f(i) = x[i] - i is non-decreasing (x[i+1] >= x[i] + 1, so f(i+1) >= f(i)). So probe the middle index mid:
- if x[mid] = mid, done;
- if x[mid] > mid, then for every j > mid, x[j] >= x[mid] + (j - mid) > j - no fixed point to the right, go left;
- if x[mid] < mid, symmetrically go right.
Each probe halves the range, so O(log n) time, O(1) space (iterative). Return -1 if the range empties.
Solution by Abhishek, Stainless, Vipul and others from the comments. *
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.
Solution:
Highlight the part between the * symbols for the answer.
* Binary search in O(log n). Because the array is sorted with no duplicates, f(i) = x[i] - i is non-decreasing (x[i+1] >= x[i] + 1, so f(i+1) >= f(i)). So probe the middle index mid:
- if x[mid] = mid, done;
- if x[mid] > mid, then for every j > mid, x[j] >= x[mid] + (j - mid) > j - no fixed point to the right, go left;
- if x[mid] < mid, symmetrically go right.
Each probe halves the range, so O(log n) time, O(1) space (iterative). Return -1 if the range empties.
Solution by Abhishek, Stainless, Vipul and others from the comments. *
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.
Binary search is optimal here - O(log n), and you cannot do better in the comparison model. (
ReplyDeleteExactly the right observation - distinctness makes x[i] - i strictly increasing, which licenses the binary se
ReplyDeleteCorrect. (replied using AI)
ReplyDeleteCorrect output, but that is a linear scan - the point of sorted + distinct is that O(log n) is available. (Also
ReplyDeleteRight idea, two bugs: (1) the recursion returns an index relative to the SUBARRAY a+mid+1, so you need mid+1+Fix
ReplyDeleteWorks but O(n); the sortedness buys you O(log n) via binary search on x[i] - i. (repl
ReplyDeleteCorrect - the invariant "x is the last index with a[h] <= h" does the work, and the final a[x] == x check handles the not-
ReplyDeleteThe stepping logic is off: temp = temp/2 (or temp + temp/2) does not maintain a shrinking [lo, hi] interval, so it can loo
ReplyDeleteCorrect. (replied using AI)
ReplyDelete