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
in the example you have given, the array is not sorted
Thanks kamal for pointing it out, corrected it.
this algorithm is wrong
Here the counter example :
array={1,2,3,3,4,5,6,7,8,9,10}
will return -1 not 3
Please check it out
The program is works for distinct integers, My bad the objective of the problem was confusing, i have corrected it. Thanks for finding it out.
Is there a similar binary search method for arrays with repeated elements or is linear scan the only way?
Thanks for post! Did you look into the case when elements are not distinct?