Problem solving with programming: Finding the magic index of the array
Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.
For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
If there no such element in the array we can return -1.
Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.
For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
If there no such element in the array we can return -1.
Read full article from Problem solving with programming: Finding the magic index of the arrayint getMagicIndex(int array[], int low, int high){if( low > high )return -1;int mid = low + (high-low)/2;if ( array[mid] == mid )return mid;if( mid > array[mid] )return getMagicIndex(array, mid+1, high);elsereturn getMagicIndex(array, low, mid-1);}
