第三篇：分治算法

news/2024/11/29 2:34:28/

第三篇：分治算法

1. 分治算法简介
2. 递归算法框架模板
3. 分治演示代码
4. 递归算法经典案例

分治算法的思想是将大问题分解成小问题，解决完一个一个小问题便解决了大问题。比如，我们想从杭州出发到徐州，可以分解成杭州到南京，然后南京再到徐州，就是这样不断分解下去，找到最小的路线拼接而成就解决了大问题。

在这里插入图片描述

1. 分治算法简介

分治法非常像递归算法，都是不断分解成容易求解的小问题最后解决一个大问题。所以分治算法经常伴随着递归算法，如果还不懂递归的朋友们可以看我上一篇文档：第二篇：递归算法。
二分查找演示：https://algorithm-visualizer.org/branch-and-bound/binary-search
在这里插入图片描述
这里我们以最常见的二分查找为例（依次分解左边部分和右半部分进行判断），
可以看到有左右两个指针，然后根据中间值来判断指针的走向。
初始值left在1的位置，right在9的位置，
中间值为：5。
要查找的值为3，和中间值对比，比5小于是：
left还是在1的位置，right就要在5的位置之前到4。
以此类推，最终就会找到3这个值。

2. 递归算法框架模板

分解：将大问题拆解成容易解决的小问题。
解决：如果问题足够小容易解决就直接返回，否则继续拆解。
合并：将各个子问题的解合并为原问题的解。

可以看到，第一步需要先分解。
要找到从大问题分解到小问题的思路，
这里必须要构造一个有序的数组才能继续二分查找。
然后一半一半的去解决。最终得到最终结果。
有点和递归类似。

3. 分治演示代码

这里以二分查找为例

public class BinarySearch {public static void main(String[] args) {int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};int index = binarySearch(array, 3);System.out.println("查找结果的下标： " + index);}/*** 二分查找** @param array     有序数组* @param searchNum 要查找的数* @return 下标*/private static int binarySearch(int[] array, int searchNum) {int left = 0;int right = array.length - 1;int mid;while (left <= right) {mid = (left + right) / 2;if (searchNum < array[mid]) {right = mid - 1;} else if (searchNum > array[mid]) {left = mid + 1;} else {return mid;}}return -1;}
}