题目：
解答：
假如不存在重复元素的话，则二分法很好实现，但此题存在重复元素，所以会比较复杂一点。
举例：
对于 [0, 1, 4, 4, 4] 这个数组，使用二分法拿出位于中间的 idx 为 2 的数字 4，然后我们发现 nums[idx] > idx；
此刻我们除了可以确认 idx2 不是魔术索引外，还可以确定 idx3 也肯定不是魔术索引。因为假如 idx3 是魔术索引的话那 idx3 的值就必须是 3，这将导致 nums[idx3] < nums[idx2]，和题目的“递增数组”矛盾。
所以，此刻魔术索引只可能出现在 [0, mid - 1] 和 [nums[mid], nums.length - 1] 这两个范围里。
1 class Solution { 2 public: 3 int findMagicIndex(vector<int>& nums) 4 { 5 return helper(nums, 0, nums.size() - 1); 6 7 } 8 9 int helper(vector<int> nums, int left, int right) 10 { 11 if (left > right) 12 { 13 return -1; 14 } 15 16 int mid = left + (right - left) /2; 17 18 if (nums[mid] < mid) 19 { 20 int ans1 = helper(nums, left, nums[mid]); 21 int ans2 = helper(nums, mid + 1, right); 22 return ans1 != -1 ? ans1 : ans2; 23 } 24 else if (nums[mid] > mid) 25 { 26 int ans1 = helper(nums, left, mid - 1); 27 int ans2 = helper(nums, nums[mid], right); 28 return ans1 != -1 ? ans1 : ans2; 29 } 30 else 31 { 32 int ans = helper(nums, 0, mid - 1); 33 return ans != -1 ? ans : mid; 34 } 35 } 36 };
原文：https://www.cnblogs.com/ocpc/p/12830543.html