Last Updated: 24 Feb, 2021
Magic Index
Easy
Asked in companies
You are given a sorted array A consisting of N integers. Your task is to find the magic index in the given array.
Note :
1. A magic index in an array A[0 ... N - 1] is defined to be an index i such that A[i] = i.
2. The elements in the array can be negative.
3. The elements in the array can be repeated multiple times.
4. There can be more than one magic index in an array.
Input Format :
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains one integer N, as described in the problem statement.
The second line of each test case contains N space-separated integers, representing the elements of the array.
Output Format :
For each test case print in a new line, one integer representing the magic index of the given array or -1 if there does not exist any magic index for the given array.
In case there is more than one magic index, return any of them.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
-10^9 <= A[i] <= 10^9
Time Limit: 1sec
Approaches
- In this brute force approach, we will check each element one by one and try to find if there is any magic index in the given array or not.
- In this approach, we will initialize our answer variable (say, ans) with ans = -1.
- Then we will iterate in the array one by one (say, loop variable i) from the beginning and check if there is any magic index in our array or not.
- If we find any index in the array such that A[i] = i, then we will assign this current index i to our answer variable ans(i.e. ans = i ) and break this loop as we have found a magic index and our task is complete.
- Finally we will print this ans variable as the answer.,
- In this approach, we will be using binary search as the given array is always sorted.
- We can apply binary search in this problem because of the fact that if at any index say ‘i’ we find that A[i] < i, then it is not possible to find the answer to the left of this index i and then we will only try to find the answer towards the right (Because if A[i] < i then say there is any index j such that j<i then A[j] < j always, because we can see that for reaching j if we shift say k indices towards the left from i then A[j] will also be at least k less than A[i] since all elements in the array are unique and A[j] has to be smaller than A[i] since the array is sorted).
- Similarly, if A[i] > i, we can not find the answer towards the right of this index i.
- So we will initialize our answer variable, say ans with -1 i.e. ans = -1.
- Then we will try to find the answer using binary search in the entire array with the range of left = 0 and right = N - 1, which will be as follows:
- mid = (left + right)/2
- Check if A[mid] = mid, if yes then assign ans = mid and right = mid - 1 because we can still find an answer to the left of this point.
- If A[mid] < mid, then left = mid + 1 and continue finding the answer.
- If A[mid] > mid, then right = mid - 1 and continue finding the answer.
- Finally, we will print our ans variable as the answer.
- When the given array has duplicate elements in it, then the normal binary search approach will fail, therefore we need a modified solution.
- In this approach, we will again be using binary search but this time we will be searching towards the left as well as the right of the current mid index.
- We will be trying to find the answer in left = 0 and right = N - 1 range.
- We will try to find the answer using binary search in the entire array with the range of left = 0 and right = N - 1, which will be as follows:
- mid = (left + right)/2 and midVal = A[mid]
- Check if A[mid] = mid, if yes then return mid as the answer.
- We will search towards the left of the current mid in the range newLeft = left and newRight = min(mid-1,midVal). If we successfully find the answer here then we will return it as the answer, or else
- We will search towards the right of the current mid in the range of newLeft = max(mid + 1,midVal) and newRight = right.
- Finally, we will return -1 if we couldn’t find the answer or return the found answer.
Similar problems
Longest Substring with K-Repeating Characters
Moderate
Posted: 8 Dec, 2025
Expression Add Operators
Hard
Posted: 8 Dec, 2025
Gray Code Transformation
Hard
Posted: 22 Feb, 2026
Minimized Maximum of Products Distributed to Any Store
Moderate
Posted: 22 Feb, 2026
Count of Subsequences with Given Sum
Moderate
Posted: 24 Feb, 2026