程序员常用的10种算法
1、二分查找算法（非递归）
1）前面我们讲过二分查找算法，是使用递归方式，下面我们讲解二分查找算法的非递归方式
2）二分查找法只适用于从有序的数列中进行查找（比如数字和字母等），将数列排序后再进行查找
3）二分查找法的运行时间为对数时间O(log2N)，即查找到需要的目标位置最多只需要log2N步，假设从[0,99]的队列(100个数，即n=100)中寻找到目标数30，则需要查找步数为log2 100，即最多查找7次。
代码实现
public class BinarySearchNoRecur {public static void main(String[] args) {// 测试int[] arr = {1,3,8,10,11,67,100};int index = binarySearch(arr, 2);System.out.println("index=" + index);}// 二分查找的非递归实现public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length -1;while (left <= right) { // 说明继续查找int mid = (left + right) / 2;if(arr[mid] == target) {return mid;} else if(arr[mid] >target) {right = mid - 1;// 需要向左边查找} else {left= mid + 1;// 需要向右边查找}}return -1;}
}
2、分治算法
代码实现
public class Hanoitower {public static void main(String[] args) {hanoiTower(5, 'A','B','C');}// 汉诺塔移动的方法// 使用分治算法public static void hanoiTower(int num, char a, char b, char c) {// 如果只有一个盘子if(num == 1) {System.out.println("第1个盘子从 " + a + "->" + c);} else {// 如果我们有 n>=2 情况，我们总是可以看作是两个盘子，1是最下面的盘子 2上面所有的盘子// 1、先把最上面的所有盘子 A->B， 移动过程中会使用到chanoiTower(num -1, a, c, b);// 2、把最下面的盘 A-> CSystem.out.println("第"+ num + "个盘子从 " + a + "->" + c);// 3、把B塔的所有盘 从B->C，移动过程中使用到a塔hanoiTower(num - 1, b, a, c);}}
}