二分搜索专题1-在非递减数组中寻找满足A[i]=i的i
在javaeye上看到了一个二分搜索相关的提问http://www.iteye.com/topic/1118606，我设计了一个简洁高效的算法，这里贴出来：
题目：对于一个非递减数组A，存在A[i]=i，求o(lgn)的算法找出i，
分析：
1,对于任意的j和i，如果j>i则A[j]>=A[i];
2,假设所求的解是I，即A[I]=I，则对任意的j，如果A[j]>j,可以得到I<j,如果A[j]<j,则j<I，如果A[j]=j，则j=I（不考虑I的多解情况）.
利用2可以得到下面的算法：
public static int search(int[] A) { int len = A.length; int start = 0; int end = len; while (start <= end) { int j = (start + end) / 2; if (A[j] == j) { return j; } if (A[j] > j) { end = j - 1; } else if (A[j] < j) { start = j + 1; } } return -1; }