A magic index in an array A[0...n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. If not, return -1. If there are more than one magic index, return the smallest one.
Example1:
Input: nums = [0, 2, 3, 4, 5] Output: 0
Example2:
Input: nums = [1, 1, 1] Output: 1
Note:
1 <= nums.length <= 1000000
/**
* @param {number[]} nums
* @return {number}
*/
var findMagicIndex = function(nums) {
return helper(nums, 0, nums.length - 1);
};
function helper(nums, left, right) {
if (left > right) return -1;
let mid = Math.floor((left + right) / 2);
let leftIndex = helper(nums, left, mid - 1);
if (leftIndex != -1) return leftIndex;
if (nums[mid] == mid) return mid;
return helper(nums, mid + 1, right);
}