Objective: Given a sorted array of distinct integers, Find the Magic index or Fixed point in the array.
Magic Index or Fixed Point: Magic index or a Fixed point in an array is an index i in the array such that A[i] = i.
Example :
int[] A = { -1, 0, 1, 2, 4, 10 }; Magic index or fixed point is : 4
Approach:
Naive approach is to do the linear scan and find the magic index in O(n).
Better solution would Modify the Binary Search – Time Complexity O(logN).
- Check mid = (start+end)/2, with A[mid], check if A[mid] = mid. if yes then return mid.
- If mid>A[mid] means fixed point might be on the right half of the array, make a recursive call to search(A, mid + 1, end).
- If mid<A[mid] means fixed point might be on the left half of the array, make a recursive call to search(A, start, mid – 1).
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MagicIndex { | |
// perform modified binary search | |
public int search(int[] A, int start, int end) { | |
if (start <= end) { | |
int mid = (start + end) / 2; | |
if (mid == A[mid]) // check for magic index. | |
return mid; | |
if (mid > A[mid]) { // If mid>A[mid] means fixed point might be on | |
// the right half of the array | |
return search(A, mid + 1, end); | |
} else {// If mid<A[mid] means fixed point might be on | |
// the left half of the array | |
return search(A, start, mid – 1); | |
} | |
} | |
return –1; | |
} | |
public static void main(String[] args) { | |
// TODO Auto-generated method stub | |
int[] A = { –1, 0, 1, 2, 4, 10 }; | |
MagicIndex m = new MagicIndex(); | |
System.out.println("Magic index " + m.search(A, 0, A.length – 1)); | |
} | |
} |
Output:
Magic index 4