内容整理自：极客时间—程序员的数学基础课 03 | 迭代法：不用编程语言自带函数，你会如何计算平方根？

1. 什么是迭代法：

? ? ? ?迭代法，简单来说，就是不断的用旧的变量值，来递推计算新的变量值。

2. 迭代法都有哪些具体应用

1. 求数值的精确或者近似解 ：典型的方法包括二分法和牛顿迭代法。
2. 在一定范围内查找目标值 ：典型的方法包括二分查找。
3. 机器学习算法中的迭代 ：相关的模型和算法有很多，比如K- 均值算法（K-means clustering）、PageRank 的马尔科夫链(Markov chain)、梯度下降法（Gradient descent）等等。 迭代法之所以在机器学习中广泛的使用，是因为很多时候，机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解 。而迭代法可以帮助学习算法逐步搜索，直至发现这种解。

3. 示例 求数值的解和查匹配记录

3.1 求数值的解

? ? ? ? 以求一个大于 1 的正数的平方根为例，如果不适用 Java 自带的 Math 类库，如何手动实现呢？

? ? ? ? 这个时间，我们就可以使用二分法查找最优解。举个例子，假如我们要求 10 的平方根，我们要先看一下 1到10 的中间值，就是 (1+10)/2 = 5.5，5.5的平方是大于10的，这个时候，我们就要看 1到5.5 的中间值，就是(1+5.5)/2 = 3.25，3.25的平方也是大于10的，然后继续，直到找到平方和等于10，或者平方和与10的差值在给定的精度范围内的值。

? ? ? ? 示例代码如下：

package match_programing.lesson3_iterator;

/**
 * @Description 求数值的精确或者近似值
 * @author hjh
 *
 */
public class SqureRoot {

	/**
	 * 计算大于 1 的正整数的平方根
	 * @param n
	 *        待求平方根的正数数
	 * @param deltaThreshold
	 *        误差的阈值 
	 * @param maxTry
	 *        二分查找的最大次数
	 * @return double
	 *        平方根的解
	 */
	public double getSqureRoot(int n, double deltaThreshold, int maxTry) {
		
		if (n <= 1) {
			return -1.0;
		}
		
		double min = 1.0, max = (double)n;
		
		for (int i = 0; i < maxTry; i++) {
			double middle = min + (max - min)/2;    // (min + max)/2 可能导致溢出
			double squre = middle * middle;
			double delta = Math.abs(squre/n -1);
			if (delta <= deltaThreshold) {
				return middle;
			}
			if (squre > n) {
				max = middle;
			}else {
				min = middle;
			}
		}
		
		return -2.0;    // 表示在指定的循环内，为找到匹配给定精度的值
	}
	
	
	/**
	 * 测试代码
	 */
	public static void main(String[] args) {
		
		SqureRoot squreRoot = new SqureRoot();
		int n = 10;
		double squre = squreRoot.getSqureRoot(n, 0.0001, 100);
		if (squre == -1.0) {
			System.out.println("请输入大于 1 的正整数 ");
		}else if (squre == -2.0) {
			System.out.println("未能找到解 ");
		}else {
			System.out.println(String.format("%d 的平方根是 %s " , n, squre));    // 10 的平方根是 3.162384033203125
		}
	}
}

3.2 查找匹配记录

? ? ? ? 使用二分法查找匹配记录，其实现的思想和上面的求正整数的平方根是一样的，区别就是：

1. 判断结束的条件不同：求平方根时，是通过判断 某个数的平方是否和输入相等或者满足给定的精度，查找匹配记录则是判断查找值是否与当前字符串相等。
2. 二分查找需要确保被搜索的空间是有序的。

? ? ? ? 二分查找的过程如下：以 a-g 中7个字符查找 f 的过程为例：

? ? ? ? 示例代码如下：

package match_programing.lesson3_iterator;

import java.util.Arrays;

/**
 * 使用二分法查找匹配的记录
 * 前提： 查找范围必须有序
 * 
 * @author Administrator
 *
 */
public class MatchRecord {
	
	/**
	 * 使用二分法，在给定的有序数组中，查找指定的字符串
	 * 
	 * @param dictionary
	 *        有序字符串数组
	 * @param wordToFind
	 *        待查找的字符串
	 * @return boolean
	 */
	public static boolean searcg(String[] dictionary, String wordToFind) {
		
		if (dictionary == null || dictionary.length == 0) {
			return false;
		}
		
		int left = 0, right = dictionary.length - 1;
		while (left <= right) {
			int middle = left + (right -left)/2;    // (right + left)/2 在right 和 left 都接近极限值时，会导致溢出
			if (dictionary[middle].equals(wordToFind)) {
				return true;
			}
			if (dictionary[middle].compareTo(wordToFind) > 0) {
				right = middle - 1;
			}else {
				left = middle + 1;
			}
		}
		
		return false;
	}
	
	
	/**
	 * 测试代码
	 */
	public static void main(String[] args) {
		String[] dictionaryString = {"i", "am", "one", "of", "the", "authors", "in", "geekbang"};
		Arrays.sort(dictionaryString);    // 二分查找必须在有序集合中使用
		String wordToFind = "i";
		
		boolean found = MatchRecord.searcg(dictionaryString, wordToFind);
		if (found) {
			System.out.println(String.format("找到了单词 %s ", wordToFind));    // 输出：找到了单词 i
		}else {
			System.out.println(String.format("未能找到单词 %s", wordToFind));
		}
	}

}

说明：文中使用的图片来自极客时间，版权归极客时间所有。

?

相关文章