find magic number 这道题值得警惕

题目：find magic number
(1) find a magic number that A[i] = i in a sorted array (monotonic increasing order), return the smallest magic number (index). return -1 if not found.
example: -2 -1 2 4
answer: 2 (a[2] == 2)

(2) (modified version of problem (1)) elements can be duplicate
example: [1, 1, 1]
answer: 1 (a[1] == 1)


(1) 标准做法是 binary search，O(logN)，比 O(N) 要好。
比如：
int magicIndex(int a[], int n){   
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == mid)
            return mid;
        else if (a[mid] < mid)
            low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

对于 (2)，虽然很多流行做法也是 binary search，O(N)。
但是实际上，binary search 的做法是错的，因为 binary search 一旦找到 a[mid] == mid，就没法找到更小的一个解了

比如：
[0, 2, 2, 2, 3]
mid = (0 + 4)/2 = 2 直接就找到 a[mid] = mid，也就是 a[2] = 2，这只是一个可行解，但是正确的解是 a[0] = 0。
根据数组元素递增（但可重复）的特性，当 a[i] > i 的时候，左右两侧都可能存在解。这对于（1）条件下的单调递增情况下是不同的，
在单调递增情况下，如果 a[i] > i，那么就必须在 i 左侧找，因为 a[i + 1] > a[i] > i，i + 1 > i => 必然有： a[i+1] > i + 1，所以右侧不可能存在解。
如果不是单调递增的情况，那么 a[i + 1] >= a[i] > i，因此当 a[i] > i 的时候，可以假定 a[i] 不变，增大 i，因此存在 a[i+1] == i + 1，因此右侧可能存在解。而显然，左侧就更可能存在解了。
而又因为是要返回最小的 magic number，也就是 index，那么就应该在左侧。

int findMagicIndex(int a[], int low, int high) {
    int mid=(low+high)/2;
    if(a[mid]==mid) {
       return mid;
    }
    else if(a[mid]<mid) {
       return findMagicIndex(a, low, a[mid]);
    }
    else { //a[mid]>mid
       return findMagicIndex(a, a[mid], high);
    }
}

上面的解答，在 case [0, 2, 2, 3] 的时候会返回 2，而正确的解是 0.

同理，下面的这个 binary search 也是错的
int findMagicIndex(int nums[], int n) {
    int low = 0, high = n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] != mid) {
            if (nums[mid] >= 0) {
                high = mid;
            } else {
                low = mid + 1;
            }
        } else {
            low = mid + 1;
        }
    }

    return low - 1;
}

正确的解答应该是从 index = 0 开始搜索，如果当前 a[i] == i，那么理解返回当前的解，因为 index 是从小到大的，所以保证了返回的是 smallest index。
如果遇到 a[i]  > i，那么应该把 i 置为 a[i]，在 index = a[i] 的位置继续判断是否 a[a[i]] == a[i]。
比如 [2, 3, 4, 5] a[0] = 2, i = 0, => a[0] > 0, i = 2; =>  a[2] = 4 => a[2] > 2 = > i = 4; => return -1;

否则，如果 a[i] < i，那么继续在右侧找。

注意：上面两种情况都是在右侧找，也就是 a[i] < i 和 a[i] > i 时，都在右侧找，不同的是，第一种情况是跳着找，第二种情况只前进一步。

代码：
int findMagicIndex(int a[], int n) {

    int i = 0;
    while (i < n) {
        if (a[i] == i) {
            return i;
        } else if (a[i] > i) {
            i = a[i];
        } else{
            i++;
        }
    }
    return -1;
}

写了这么多，希望好心人给加点米 😊

试了下用binary search解第二问，复杂度在极端情况下从二分退化成了线性，但在随机化test case情况下复杂度还是好于O(N)（也可能是测试设计不够完善）
代码如下，欢迎补充test case

1. import java.util.Arrays;
   
2. import java.util.Random;
   
3. 
   
4. /**
   
5. * find magic number
   
6. * (1) find a magic number that A[i] = i in a sorted array (monotonic increasing order), return the smallest magic number (index). return -1 if not found.
   
7. * example: -2 -1 2 4
   
8. * answer: 2 (a[2] == 2)
   
9. *
   
10. * (2) (modified version of problem (1)) elements can be duplicate
    
11. * example: [1, 1, 1]
    
12. * answer: 1 (a[1] == 1)
    
13. */
    
14. public class FindMagicNumber {
    
15.     public static void main(String[] args) {
    
16.         int[] test1 = new int[] {-2, -1, 3, 4};
    
17.         findMagicNumber1(test1);
    
18.         findMagicNumber2(test1);
    
19. 
    
20.         int[] test2 = new int[] {};
    
21.         findMagicNumber1(test2);
    
22.         findMagicNumber2(test2);
    
23. 
    
24.         int[] test3 = new int[] {0, 1, 2, 3, 4};
    
25.         findMagicNumber1(test3);
    
26.         findMagicNumber2(test3);
    
27. 
    
28.         int[] test4 = new int[] {1, 1, 1};
    
29.         findMagicNumber2(test4);
    
30. 
    
31.         int[] test5 = new int[] {0, 1, 1, 2, 3};
    
32.         findMagicNumber2(test5);
    
33. 
    
34.         int[] test6 = new int[] {-1, -1, -1, 3, 4};
    
35.         findMagicNumber2(test6);
    
36. 
    
37.         int[] test7 = new int[] {-1, -1, -1, 100, 100};
    
38.         findMagicNumber2(test7);
    
39. 
    
40.         int[] test8 = new int[10000];
    
41.         for (int i = 0; i < test8.length; i++) {
    
42.             test8[i] = i + 1;
    
43.         }
    
44.         findMagicNumber2(test8);
    
45. 
    
46.         int[] test9 = new int[10000];
    
47.         for (int i = 0; i < test9.length; i++) {
    
48.             test9[i] = i;
    
49.         }
    
50.         findMagicNumber1(test9);
    
51.         findMagicNumber2(test9);
    
52. 
    
53.         int[] test10 = new int[10000];
    
54.         for (int i = 0; i < test10.length; i++) {
    
55.             if (i > 4998) {
    
56.                 test10[i] = i + 1;
    
57.             } else {
    
58.                 test10[i] = i;
    
59.             }
    
60.         }
    
61.         findMagicNumber2(test10);
    
62. 
    
63.         int[] test11 = new int[10000];
    
64.         for (int i = 0; i < test11.length; i++) {
    
65.             if (i < 4999) {
    
66.                 test11[i] = i + 1;
    
67.             } else {
    
68.                 test11[i] = i;
    
69.             }
    
70.         }
    
71.         findMagicNumber2(test11);
    
72. 
    
73.         Random rand = new Random();
    
74.         int[] test12 = new int[10000];
    
75.         int sum = 0;
    
76.         int found = 0;
    
77.         int tn = 10000;
    
78.         for (int k = 1; k <= tn; k++) {
    
79.             for (int i = 0; i < test12.length; i++) {
    
80.                 test12[i] = rand.nextInt(10000) - rand.nextInt(rand.nextInt(300) + 1);
    
81.             }
    
82.             Arrays.sort(test12);
    
83.             found += findMagicNumber2(test12, false) != -1 ? 1 : 0;
    
84.             sum += count2;
    
85.         }
    
86.         System.out.println("Average recursion count is: " + (sum / tn) + ", found " + found + " cases");
    
87.     }
    
88. 
    
89.     static int count1 = 0;
    
90.     static int count2 = 0;
    
91. 
    
92.     public static int findMagicNumber1(int[] nums) {
    
93.         count1 = 0;
    
94.         if (nums.length == 0) {
    
95.             System.out.println("Find Magic Number 1");
    
96.             System.out.println("Test case is: " + Arrays.toString(nums));
    
97.             System.out.println("O(N) = " + nums.length + ", Recursion count = " + count1);
    
98.             System.out.println("Result is: -1");
    
99.             System.out.println();
    
100.             return -1;
     
101.         }
     
102. 
     
103.         int l = 0;
     
104.         int r = nums.length - 1;
     
105. 
     
106.         while (l < r) {
     
107.             count1++;
     
108.             int m = (l + r) >> 1;
     
109.             if (nums[m] == m) {
     
110.                 r = m;
     
111.             } else if (nums[m] < m) {
     
112.                 l = m + 1;
     
113.             } else {
     
114.                 r = m - 1;
     
115.             }
     
116.         }
     
117.         System.out.println("Find Magic Number 1");
     
118.         System.out.println("Test case is: " + Arrays.toString(nums));
     
119.         System.out.println("O(N) = " + nums.length + ", Recursion count = " + count1);
     
120.         System.out.println("Result is: " + (nums[l] == l ? l : -1));
     
121.         System.out.println();
     
122. 
     
123.         return nums[l] == l ? l : -1;
     
124.     }
     
125. 
     
126.     public static int findMagicNumber2(int[] nums, boolean print) {
     
127.         count2 = 0;
     
128.         int res = findMagicNumber2Impl(nums, 0, nums.length - 1);
     
129.         if (print) {
     
130.             System.out.println("Find Magic Number 2");
     
131.             System.out.println("Test case is: " + Arrays.toString(nums));
     
132.             System.out.println("O(N) = " + nums.length + ", Recursion count = " + count2);
     
133.             System.out.println("Result is: " + (res < nums.length ? res : -1));
     
134.             System.out.println();
     
135.         }
     
136.         return res < nums.length ? res : -1;
     
137.     }
     
138. 
     
139.     public static int findMagicNumber2(int[] nums) {
     
140.         return findMagicNumber2(nums, true);
     
141.     }
     
142. 
     
143.     private static int findMagicNumber2Impl(int[] nums, int l, int r) {
     
144.         count2++;
     
145.         if (nums.length == 0) {
     
146.             return Integer.MAX_VALUE;
     
147.         }
     
148.         if (l >= r) {
     
149.             return l < nums.length ? (nums[l] == l ? l : Integer.MAX_VALUE) : Integer.MAX_VALUE;
     
150.         } else {
     
151.             int m = (l + r) >> 1;
     
152.             if (nums[m] == m) {
     
153.                 return findMagicNumber2Impl(nums, l, m);
     
154.             } else if (nums[m] > m) {
     
155.                 int r1 = findMagicNumber2Impl(nums, l, m - 1);
     
156.                 if (r1 < Integer.MAX_VALUE) {
     
157.                     return r1;
     
158.                 } else {
     
159.                     return findMagicNumber2Impl(nums, nums[m], r);
     
160.                 }
     
161.             } else {
     
162.                 int r1 = findMagicNumber2Impl(nums, l, nums[m]);
     
163.                 if (r1 < Integer.MAX_VALUE) {
     
164.                     return r1;
     
165.                 } else {
     
166.                     return findMagicNumber2Impl(nums, m + 1, r);
     
167.                 }
     
168.             }
     
169.         }
     
170.     }
     
171. }
     

复制代码

经网友提醒，（1）中给出的原解答是错的，因为应对 case [0, 1, 2] 会得出错解答。

正确的应该如下：
int findMagicIndex(int a[], int n) {
    int low = 0, high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] >= mid) // 找到一个解之后，继续往左找。
            high = mid - 1;
        else low = mid + 1;
    }

    return low;
}


原理：一旦找到一个解，那么要么左边邻居也是解，要么左边不可能存在解。因为 index i 是连续的，而如果 a[i] 不连续的话，那么一旦错位，就不可能对齐了，所以一个可行解的邻居不是解的话，那么其它地方就不可能有解了。

这道题可以用二分法的前提是能保证在最后一个A=i 之后，都有A > i, 在第一个A=i 之前都有A < i. 这样就可以用lower bound的二分法变种

1. 
   
2. arr = [ 0, 1, 3, 4]
   
3. 
   
4. left = 0
   
5. right = len(arr)
   
6. while left < right:
   
7.     mid = left + (right - left)/2
   
8.     if arr[mid] >= mid:
   
9.         right = mid
   
10.     else:
    
11.         left = mid + 1
    
12. print arr[right], right

复制代码

如果数组是 0,1,1,4，就无法用二分法了

这样最坏还是O(N), 顺便1的那个二分也有点问题

（1）的二分显然不对。。。
假设有对于一个{a_i}，a[i] = i。应该返回的是0，但按照这个写法，会在mid = (1+n-1)/2之后直接返回。。。

我之前都没有注意到这个

谢谢题主分享！
另外是不是也可以把二分法给这么改一下，作为一个铺垫算法，显示我们的优化过程：
弄多次二分法，每次二分法找到一个magic number 之后，对于左边subarray 再做一次，一直做到subarray回复没有magic number 为止……

AresLuo 发表于 2020-7-13 00:12
谢谢题主分享！
另外是不是也可以把二分法给这么改一下，作为一个铺垫算法，显示我们的优化过程：
弄多次二 ...

这样在最坏情况下还不如直接遍历

(1) 的解法略有瑕疵，在a[mid] == mid的情况下应该记录下mid的值并继续对左侧进行二分。

即使是第一种情况如果求最小解，楼主考虑过[0,1,2,3,4,5]的binary解法么