力扣面试题 41 - 魔术索引 C语言解法 二分查找

题目：

魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1:

 输入：nums = [0, 2, 3, 4, 5]
 输出：0
 说明: 0下标的元素为0

示例2:

 输入：nums = [1, 1, 1]
 输出：1

说明:

1. nums长度在[1, 1000000]之间
2. 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

思路：

1. 采用二分查找与递归结合的思想。
2. 因为数组可能存在重复元素的情况，所以优先检查左侧是否有更小的魔术索引，再检查当前索引是否为魔术索引，最后检查右侧范围。
3. 找到索引后立即返回，无需继续寻找。

代码如下：

int BinarySearch(int* nums, int low, int high) {if (low > high) {return -1;}int mid = low + (high - low) / 2;// 优先检查左侧是否有更小的魔术索引int left = BinarySearch(nums, low, mid - 1);if (left != -1) {return left;}// 检查当前索引是否为魔术索引if (nums[mid] == mid) {return mid;}// 检查右侧范围return BinarySearch(nums, mid + 1, high);
}
int findMagicIndex(int* nums, int numsSize) {return BinarySearch(nums, 0, numsSize - 1);
}