正确解看此链接
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] >= middle
int 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");
}
}
}
分享到:
相关推荐
计算机二分法的算法步骤-五大常用算法之一:分治算法,算法数据结构 五大常用算法
对于区间[a,b]上连续不断且f(a)·f(b)的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法。 算法:当数据量很大适宜采用该...
二分法解非线性方程C++代码
自己设计的matlab算法,针对二分法的
使用二分法解线性方程二分法解线性方程二分法解线性方程
二分法实现.txt二分法实现.txt二分法实现.txt
matlab二分法算法,实测可用,直接调用该函数即可得到目标解
九章算法之二分法(Binary Search) 适合找工作的小伙伴
用二分法求方程x^3+4x^2-10=0在区间的(1,4)的实根。要求精确到小数点后第四位。 本程序可以相对的修改,而且不仅仅是代码而已,还包含了界面
本文档使用二分法求解非线性方程组,使用扫描算法求得解的存在区间,然后用二分法求解。具体算法实现参照西安交通大学版数值分析课程
作业, 用二分法求方程近似解 C#编写
是一个c++的用二分法求方程根的好算法,快来下载吧!
算法-分治- 二分法(包含源程序).rar
给定的表中用二分法查找指定数 给定的表中用二分法查找指定数 给定的表中用二分法查找指定数
二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
二分法排序算法 C语言实现 个人爱好 希望相互学习
Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
二分法算法 弦截法算法 matlab,看看有用没
比二分法更快的算法-算法问题:扔杯子的几种方法,排序算法数据结构 最快的排序算法
matlab开发-最小性的二分法算法。二分法求H无穷大的GAMA值