给定一个排好升序的数组A[1]、A[2]、.....、A[n]，其元素的值都两两不相等，请设计一高效算法找出中间所有A[i]=i的下标。
1，这个题目中，数组A[i]应该是个整数数组
2，由升序+两两不等可知，A[i]是个递增的数列
把A[i]连成一条线，则与直线y=x只有一个交点（或者有仅有一段重合），即满足：
如果A[i]>i，则点A[i]在直线y=x的上半部，即 对任意j>i,都有A[j]>j，i以后的区间可以抛弃；
如果A[i]<i，则点A[i]在直线y=x的下半部，即 对任意j<i,都有A[j]<j，i以前的区间可以抛弃；
这篇博客恰好是这个问题的完美解法：http://openmind.iteye.com/blog/1320859
高效是指时间复杂度低吗，2分查找
如果这是一个整形的数组，二分法应该很快很快
差不多这个意思，没优化，只实现功能了，凑合看吧。。。
因两两不相等，且升序，那么 a【i】 == i 的，都是前面连续的。
[code="java"]
public static final int[] a = new int[]
{ 1, 2, 3, 7, 8, 9 };
public static void main(String[] args)
{
int x = 1, y = a.length, j = 0;
if (a[y - 1] == y)
{
// 全都是
System.out.println(y);
} else
{
while (x != y)
{
j = (y + x) / 2;
if (a[j - 1] == j)
{
x = j;
if (x + 1 == y)
{
x = y;
}
} else
{
y = j;
}
}
System.out.println(j);
}
}
[/code]
我的想法是加强你题目的条件，假设你的数组是整形数组
然后做以下推理：
1）对任一元素A[i]，若ii不存在A[i']=i'
2）对任一元素A[i]，若i>A[i]，则对任意i' 3）假设存在A[i]=i,A[j]=j，ij，不妨设i 4）假设存在A[i]=i,A[j]=j，ij，不妨设ii'
以上几点都容易证明，
1）指的是A[i]在i的右侧时，右侧不存在符合的值
2）指的是A[i]在i的左侧时，左侧不存在符合的值
3）和4）指的是如何存在，只可能是唯一的一段连续整型的下标符合条件的值
于是命题是找到最小的l符合A[l]=l和最大的r符合A[r]=r
为此可以先找到l至r段中任意一个元素m，然后分别找m两边的l和r
findm(a,b):找到元素m,用推断1和2及二分法找到第一个满足A[i]=i的值；即若二分点i=A[i]，则m=i，然后找l和r，返回；否则若iA[i]，则a=i，继续findm(a,b)；
findm(a,b):
i=(a+b)/2;
if i=A[i]: m=i; findLeft(a,m); findRight(m,b); return;
if a+1>=b: return;
if i<A[i]: findm(a,i);
else: findm(i,b);
findleft(a,m):找到元素l，用推断3和4及二分法找A[i]=i，并不断修正，即若二分点i满足A[i]=i，则m=i，若不满足，则a=i；继续findLeft(a,m)，直到a=m为止，置l=m；
findLeft(a,m):
if a=m: l=m; return;
i=(a+m)/2;#下取整
if i=A[i]:findLeft(a,i);
else: findLeft(i,m);
findRight(m,b):找到元素r，用推断3和4及二分法找A[i]=i，并不断修正，即若二分点i满足A[i]=i，则m=i，若不满足，则b=i；继续findRight(m,b)，直到b=m为止，置r=m；
findRight(m,b):
if b=m; r=m; return;
i=(m+b)/2;#上取整
if i=A[i]:findRight(i,b);
else: findRight(m, i);
时间复杂度可参考二分法的
数组B[i]是数组A[i]的降序排列，
if(0==B[i]-A[i])
那么必然A[i]=i
我这里有个log(n)的算法：http://openmind.iteye.com/blog/1320859
楼上正解，二分法找出符合条件的数组下标区间，再在这个区间内匹配！
我也来贴一段伪代码：
int index = 0;
while(index < nums.length) {
double value = nums[index];
int n = (int) value;
if (n != value || index > n) {
index ++;
continue;
}
if (index == n) {
System.out.println(index);//打印下标
index ++;
continue;
}
index = n;
}
[code="java"] // 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 };[/code]
这个问题,二分法貌似不太适用,
用二分法,无法是在 A[n]=m ; n>m 或者 n<m之间找区间,
但是看上面的这个数组.上面的数组会在6,11,14,19的时候出现 n=m的情况
n<=14以前,都是n>=m;
但是到了 14<n<=19 这个区间,都是n<=m的.
所以区间法(二分法)不靠谱.
所以我觉得用hash比较靠谱
之前对题目加了个整形约束，下面是我对非整形情况的处理，思路还是尽可能的丢弃不可能的区间：
假如给定任意区间A[i]至A[j]，判断其内部是否可能有符合的元素，提出以下论点：
1，j-(i+1)必须大于等于1，即i至j中间还有元素
2，A[j-1]的整数部分-A[i]的整数部分必须大于等于1
3，A[i]的整数部分必须小于j-1
4，A[j]的整数部分必须大于i+1
以上论点也是比较容易证明的
函数check（index）：判断A[index]是否是符合的元素
函数subFind(int first, int last)：判断first至last中是否可能有符合的元素，如果有缩小范围计算，即选取first和last之间任意一点i，判断first+1至i区间是否符合元素；以及i+1至last-1之间是否有符合的元素，依次递进。
下面给一段代码：
其中，由于java数组是从0开始的，加了偏移量；选取点的策略使用了中值法（可以有其他选择）；
[code="java"]
public class FindTester {
//static double[] a = { -0.9, -0.6, 0, 0.2, 0.3, 6,
// 6.1, 6.2, 6.3, 6.4, 6.5, 6.7, 6.8, 6.9, 11, 11.1, 11.2, 14 };
static double[] a = { -0.9, -0.6, 0, 0.2, 0.3, 6,
6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14 };
public static void main(String[] args) {
subFind(0, a.length-1);
}
public static void subFind(int first, int last) {
check(first);
check(last);
if (Math.min(last - first - 1, (int) a[last-1] - (int) a[first]) >= 1
&& ((int) a[first] < (last + 1) - 1 && (int) a[last] > (first + 1) + 1)) {
int i = (first + last) / 2;
if (first + 1 == i) {
check(i);
} else {
subFind(first + 1, i);
}
if (i + 1 == last - 1) {
check(i + 1);
} else if (i + 1 < last - 1) {
subFind(i + 1, last - 1);
}
}
}
public static void check(int index) {
System.out.printf("##check %d ##\n", index+1);
if (a[index] == index + 1) {
System.out.printf("a%d\n", index+1);
}
}
}
[/code]
-0.9, -0.6, 0, 0.2, 0.3, 6, 6.1, 6.2, 6.3, 6.4, 11, 11.1, 11.2, 14
打印为
##check 1 ##
##check 14 ##
a14
##check 2 ##
##check 7 ##
##check 3 ##
##check 4 ##
##check 5 ##
##check 6 ##
a6
##check 8 ##
##check 13 ##
##check 9 ##
##check 10 ##
##check 11 ##
a11
##check 12 ##
很不巧，每个元素都检查了
-0.9, -0.6, 0, 0.2, 0.3, 6, 6.1, 6.2, 6.3, 6.4, 6.5, 6.7, 6.8, 6.9, 11, 11.1, 11.2, 14
打印为
##check 1 ##
##check 18 ##
##check 2 ##
##check 9 ##
##check 3 ##
##check 5 ##
##check 6 ##
a6
##check 8 ##
##check 10 ##
##check 17 ##
只检查了部分
这道题题目并没有说数组元素的是否为整数，是否可以为负数。
最坏的假设，假设数组元素为小数可以为负数。那么只能通过遍历来查找。
稍微好点的假设，假设数组元素为整数可以为负数。那么通过两次二分查找，找到解段的开始位置和结束位置。
最好的假设，假设数组元素为整数且不能为负数。那么通过一次二分查找，找到解段的结束位置，开始位置必定是第一个数组元素（或者无解）。
在A[1] A[n] 除了1 2 的情况外：
3.A[n/2] < n/2 A[1]-A[n/2] 不需要比较 因为不满足
4.A[n/2] > n/2 A[n/2] - A[n] 不需要比较 因为不满足
如此下去就行了 ，二分法 妥妥的
public static int[] extract(int[] digs){
if(digs == null || digs.length <= 0){
return digs;
}
List<Integer> result = new ArrayList<Integer>();
for ( int i = 0, n = digs.length; i < n; i++){
if( i == digs[i]){
result.add(i);
}else{
i = digs[i];
}
}
return ArrayUtils.toPrimitive(result.toArray(new Integer[]{}));
}
[code="java"]
public static int[] extract(int[] digs){
if(digs == null || digs.length <= 0){
return digs;
}
List<Integer> result = new ArrayList<Integer>();
for ( int i = 0, n = digs.length; i < n; i++){
if( i == digs[i]){
result.add(i);
}else{
i = digs[i];
}
}
return ArrayUtils.toPrimitive(result.toArray(new Integer[]{}));
}
[/code]
就是二分递归吧
一直波动如何是好？
[img]http://dl2.iteye.com/upload/attachment/0089/6300/451efe59-1a42-3595-b64b-491c4719ba10.png[/img]
二分法可以的啊，Arrays.sort....
就算Double也可以调用doubleToLongBits去处理的。
![http://dl2.iteye.com/upload/attachment/0089/6300/451efe59-1a42-3595-b64b-491c4719ba10.png[/img]](http://dl2.iteye.com/upload/attachment/0089/6300/451efe59-1a42-3595-b64b-491c4719ba10.png%5B/img%5D){kind=link}