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 <= 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.