12: Find Magic Index

uuuouou

对于sorted intarray，我们有intarray【i】-i是单调不减的，这是因为(intarray[i+1]-(i+1)) - (intarray【i】-i) = intarray[i+1]-intarray【i】-1，由于intarray[i+1]>=intarray【i】+1，所以intarray[i+1]-intarray【i】-1>=0，所以题目转换为求0在数组[intarray【i】-i]中的lower_bound，二分查找即可在O(logN)内完成

1. class Solution {
   
2. public:
   
3.     int getMagicIndex(vector<int> &A) {
   
4.         if(A.empty()) return -1;
   
5.         int n = A.size();
   
6.         if(A[0] > 0 || A[n-1] < n-1) return -1;
   
7.         int l = -1, r = n-1;
   
8.         while(l+1 < r){
   
9.             int m = (l+r) >> 1;
   
10.             if(A[m] >= m) r = m;
    
11.             else l = m;
    
12.         }
    
13.         return A[r] == r ? r : -1;
    
14.     }
    
15. };

复制代码