Find Magic Index in Sorted Array

Given a sorted array A consisting of N integers, your task is to find the magic index in the given array, where the magic index is defined as an index i such that A[i] = i.

Example:

Input:

T = 1
N = 5
A = [-1, 0, 1, 3, 5]

Output:

3

Explanation:

For the given array, A[3] = 3, which means index 3 is a magic index.

Constraints:

1

Question

Find Magic Index in Sorted Array

Given a sorted array A consisting of N integers, your task is to find the magic index in the given array, where the magic index is defined as an index i such that A[i] = i.

Example:

Input:

T = 1
N = 5
A = [-1, 0, 1, 3, 5]

Output:

Explanation:

For the given array, A[3] = 3, which means index 3 is a magic index.

Constraints:

1 <= T <= 10
1 <= N <= 10⁵
-10⁹ <= A[i] <= 10⁹

Note:

A magic index is an index such that A[i] = i.
The elements in the array can be negative and can repeat.
There can be more than one magic index; you can return any of them.
If no magic index exists, return -1.
You do not need to print anything; just implement the provided function.

Accepted Answer

Find the magic index in a sorted array where A[i] = i.

Iterate through the array and check if A[i] = i for each index i.
Since the array is sorted, you can optimize the search using binary search.
Return the index if found, else return -1.