Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

# Magic Index

Easy
0/40
Average time to solve is 20m
Contributed by

## Problem statement

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.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 10
1 <= N <= 10^5
-10^9 <= A[i] <= 10^9

Time Limit: 1sec
``````
##### Sample Input 1 :
``````1
5
-5 -1 2 1 9
``````
##### Sample Output 1 :
``````2
``````
##### Explanation For Sample Input 1 :
``````The output is 2 because A[2] = 2 and hence 2 is the magic index.
``````
##### Sample Input 2 :
``````2
5
2 3 4 5 6
6
-1 -1 -1 4 4 4
``````
##### Sample Output 2 :
``````-1
4
``````
Console