面试题08.03.魔术索引

链接：面试题08.03.魔术索引
难度：Easy
标签：数组、二分查找
简介：魔术索引。 在数组 A[0...n-1]中，有所谓的魔术索引，满足条件 A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组 A 中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

题解 1 - typescript

• 编辑时间：2020-07-31
• 执行用时：92ms
• 内存消耗：38.6MB
• 编程语言：typescript
• 解法介绍：二分查找。

function findMagicIndex(nums: number[]): number {
  return _find(0, nums.length);
  function _find(l: number, r: number): number {
    if (l >= r) return -1;
    const mid = (l + r) >> 1;
    const num = nums[mid];
    if (num === mid) return mid;
    const left = _find(l, mid);
    if (left === -1) return _find(mid + 1, r);
    else return left;
  }
}