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
profile
Contributed by
203 upvotes
Asked in companies
MicrosoftFacebookAdobe

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
Full screen
Console