力扣面试题 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
说明:
- nums长度在[1, 1000000]之间
- 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本
思路：
- 采用二分查找与递归结合的思想。
- 因为数组可能存在重复元素的情况，所以优先检查左侧是否有更小的魔术索引，再检查当前索引是否为魔术索引，最后检查右侧范围。
- 找到索引后立即返回，无需继续寻找。
代码如下：
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);
}