#面試編程題#給定一個(gè)數(shù)組A，其中有一個(gè)位置被稱(chēng)為Magic Index，含義是：如果i是Magic Index，則A[i] = i。假設(shè)A中的元素遞增有序、且不重復(fù)，請(qǐng)給出方法，找到這個(gè)Magic Index。當(dāng)A中允許有重復(fù)的元素，該怎么辦呢？
第一個(gè)，不重復(fù)，很簡(jiǎn)單，用二分查找就OK了。對(duì)吧
1 int find_magic_index2(int *list, int count) {
2 int low = 0, high = count - 1;
3 while (high > low) {
4 int idx = (high + low) / 2;
5 if (idx == list[idx])
6 return idx;
7 else if (list[idx] > idx) {
8 high = idx - 1;
9 }
10 else
11 low = idx + 1;
12 }
13
14 return -1;
15 }
第二個(gè)，可重復(fù)的，該怎么辦?從頭到尾走一邊，總歸是可以的嘛。:)。我的想法是，如果a[i]等于i的話，找到了；如果大于i的話，讓i=a[i]，不然i++繼續(xù)找。這樣最差的情況才是O(n)
至于為什么可以讓i=a[i]，原因由于數(shù)列是遞增的，所以數(shù)組元素在{i, a[i]}的區(qū)間中，肯定不可能存在magic index。這樣看上去是不是跳躍著前進(jìn)啊。:)
1 int find_magic_index (int *list, int count) {
2 int i=0;
3 while (i<count) {
4 if (list[i] == i)
5 return i;
6 else if (list[i] > i)
7 i = list[i];
8 else
9 i++;
10 }
11 return -1;
12 }