2014-03-20 03:01
题目：给定一个已按升序排序的数组，找出是否有A[i] = i的情况出现。
解法1：如果元素不重复，是可以严格二分查找的。
代码：
1 // 9.3 Given a unique sorted array, find a position where A[i] = i, if one exists. 2 #include <cstdio> 3 #include <vector> 4 using namespace std; 5 6 int main() 7 { 8 vector<int> v; 9 int n; 10 int i; 11 int ll, rr, mm; 12 13 while (scanf("%d", &n) == 1 && n > 0) { 14 v.resize(n); 15 for (i = 0; i < n; ++i) { 16 scanf("%d", &v[i]); 17 } 18 if (v[0] > 0 || v[n - 1] < n - 1) { 19 mm = -1; 20 } else { 21 ll = 0; 22 rr = n - 1; 23 while (ll <= rr) { 24 mm = (ll + rr) / 2; 25 if (v[mm] < mm) { 26 ll = mm + 1; 27 } else if (v[mm] > mm) { 28 rr = mm - 1; 29 } else { 30 break; 31 } 32 } 33 if (ll > rr) { 34 mm = -1; 35 } 36 } 37 printf("%d ", mm); 38 39 v.clear(); 40 } 41 42 return 0; 43 }
解法2：如果元素可能存在重复，那么会出现无法确定答案在左边还是右边的时候。比如{-1, 3, 3, 3, 3}，后面的连续4个‘3’中有A[i]<i，有A[i]>i，也有A[i]=i的。这种情况下就得两边都进行查找了。在没有重复的时候，还是可以二分的，因此总体复杂度介于O(log(n))和O(n)之间，依数据好坏而变。
代码：
1 // 9.3 Given a sorted array, find a position where A[i] = i, if one exists. The array may have duplicates. 2 #include <cstdio> 3 #include <vector> 4 using namespace std; 5 6 int findMagicIndex(vector<int> &v, int start, int end) 7 { 8 if (start > end || start > (int)v.size() - 1 || end < 0) { 9 return -1; 10 } 11 int mid = (start + end) / 2; 12 if (v[mid] == mid) { 13 return mid; 14 } 15 16 int res = findMagicIndex(v, start, (mid - 1 < v[mid] ? mid - 1 : v[mid])); 17 if (res >= 0) { 18 return res; 19 } 20 res = findMagicIndex(v, (mid + 1 > v[mid] ? mid + 1 : v[mid]), end); 21 return res; 22 } 23 24 int main() 25 { 26 vector<int> v; 27 int n; 28 int i; 29 30 while (scanf("%d", &n) == 1 && n > 0) { 31 v.resize(n); 32 for (i = 0; i < n; ++i) { 33 scanf("%d", &v[i]); 34 } 35 printf("%d ", findMagicIndex(v, 0, n - 1)); 36 37 v.clear(); 38 } 39 40 return 0; 41 }