答复: 一道算法题，百思不得其解，求指导[非降序列找目标项，二分法变体]
正确解看此链接
http://www.cnblogs.com/sunyongyue/archive/2010/12/04/1896675.html
这个条件粗看起来不是很靠谱，事实上却很好用

代码实现如下，

import java.util.Arrays;public class AiEqualsISearcher {private static int ARR_LENGTH = 100;private int[] numArr = new int[ARR_LENGTH];private int stepCount = 0;private void init() {int targetElement = (int) (Math.random() * (ARR_LENGTH - 1));numArr[targetElement] = targetElement;int num = targetElement - 1;while (num >= 0) {int tmp = (int) (Math.random() * 3);numArr[num] = numArr[num + 1] - tmp;if (numArr[num] == num) {numArr[num] = num - 1;}num--;}for (int i = targetElement + 1; i < ARR_LENGTH; i++) {int tmp = (int) (Math.random() * 5);numArr[i] = numArr[i - 1] + tmp;if (numArr[i] == i) {numArr[i] = i + 1;}}System.out.println("the num arr init as " + Arrays.toString(numArr));System.out.println("the target index is " + targetElement);}private int search(int start, int end) {System.out.println("check a[" + start + "," + end + "]");stepCount++;int middle = (start + end) / 2;if (numArr[middle] == middle) {return middle;}if (start >= end) {return -1;}if (end >= numArr[middle]) { // && numArr[end] >= middleint result = search(middle + 1, end);if (result != -1) {return result;} else {return search(start, middle - 1);}} else {System.out.println("a[" + middle + "," + end + "] no need to check");return search(start, middle - 1);}}public static void main(String[] args) {AiEqualsISearcher searchAi = new AiEqualsISearcher();searchAi.init();System.out.println("\nstart to search...");int i = searchAi.search(0, AiEqualsISearcher.ARR_LENGTH - 1);if (i >= 0) {System.out.println("find a[" + i + "]=" + i + " with "+ searchAi.stepCount + " steps ");} else {System.out.println("can't find the element");}}}