首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法--分治算法

算法--分治算法

作者头像
奋飛
发布2019-08-15 16:27:49
5210
发布2019-08-15 16:27:49
举报
文章被收录于专栏:Super 前端Super 前端

版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

                 本文链接:[https://ligang.blog.csdn.net/article/details/83866378](https://ligang.blog.csdn.net/article/details/83866378) 

分治算法

分而治之,把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。如:二分法、快速排序、归并排序,二叉树遍历(先遍历左子树再遍历右子树)等。

步骤:

  • 分解:将原有问题分解为若干规模较小,相对独立,与原问题形式相同的子问题;
  • 解决:若子问题容易解决,则直接解;否则继续分解为更小的子问题,直到容易解决;
  • 合并:将已求解的各个子问题的解逐步合并为原问题的解。

经典递归案例:

示例: 归并排序

详见:javascript排序算法

示例: 二分查找法(二分法)

二分查找也称折半查找,其要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

  • 假设表中元素是按升序排序,将中间位置的数与要查找的数做比较;
  • 如果大于该数,则在其左侧子表中继续查找;否则在右侧子表中继续查找;
  • 重复上述步骤,知道查找成功或者不存在。
function binarySearch (find, ary, low, high) {
	let mid = Math.ceil((low + high)/2)
	if (low <= high) {
		if (ary[mid] === find) {
			return mid
		} else if (ary[mid] > find) {
			return binarySearch(find, ary, 0, mid - 1)
		} else {
			return binarySearch(find, ary, mid + 1, high)
		}
	}
	return -1
}

let ary = [1, 2, 3, 4, 5, 6, 7]
binarySearch(3, ary, 0, ary.length - 1)

改造参数

function binarySearch (find, ary) {
	let low = 0
	let high = ary.length - 1
	return (function f (low, high) {
		let mid = Math.ceil((low + high)/2)
		if (low <= high) {
			if (ary[mid] === find) {
				return mid
			} else if (ary[mid] > find) {
				return f(0, mid - 1)
			} else {
				return f(mid + 1, high)
			}
		}
		return -1
	})(low, high)	
}

let ary = [1, 2, 3, 4, 5, 6, 7]
binarySearch(3, ary)
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年11月08日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 分治算法
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档