二分搜索专题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;  
}  

解析：
当A[j]>j时，抛弃[j,end]的区间,当A[j]<j时，抛弃[start,j]的区间

欢迎网友的指导。

评论

6 楼 beck5859509 2013-09-25  

这个只能搜到一个，题目中如果数组中存在多个a[j]=j的情况不满足。

5 楼 unique.wu 2013-09-25  

排序好的数组，不用二分法，用什么，任意类型都可以的啊，只要能够比较。。

4 楼 414149609 2013-09-23  

OpenMind 写道

我这篇博客有点问题，要改成递增（而不是非递减）数列就没有问题。

刚才写错了

public static double[] ff = new double[] { -1, -0.9, -0.6, 0, 0.2, 0.3, 6, 6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14, 16, 17, 17.1, 18.2, 19 };

3 楼 414149609 2013-09-23  

OpenMind 写道

我这篇博客有点问题，要改成递增（而不是非递减）数列就没有问题。

拿A[n]=m的情况来说,你如何抛掉那些不可能的区间

比如就这个例子

public static double[] ff = new double[] { -1, -0.9, -0.6, 0, 0.2, 0.3, 6,   
3.        6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14, 16, 17, 17.1, 18.2, 19 };

如果你的第一次落的点在11里面, 你要抛掉后面还是前面的?? 无论前面还是后面都会有
n>m , n<m ,n=m的情况

2 楼 OpenMind 2013-09-23  

我这篇博客有点问题，要改成递增（而不是非递减）数列就没有问题。

1 楼 414149609 2013-09-23  

	// 6,11,14,19   注意:从14之后开始,"下标"是是小于"内容",但是最终在19相等了
	public static double[] ff = new double[] { -1, -0.9, -0.6, 0, 0.2, 0.3, 6,
			6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14, 16, 17, 17.1, 18.2, 19 };

这个问题,二分法貌似不太适用,
用二分法,无法是在 A[n]=m  ; n>m 或者 n<m之间找区间,

但是看上面的这个数组.上面的数组会在6,11,14,19的时候出现 n=m的情况

n<=14以前,都是n>=m;
但是到了   14<n<=19 这个区间,都是n<=m的.

所以区间法(二分法)不靠谱.

所以我觉得用hash比较靠谱