二分分割

[[TOC]]

说明

本章节是很多内容的基础

• 二分查找
• 线段树

问题引入

有一排盒子,分别是$1,2,\cdots ,n$,只有一个盒子有一个铁球,其它的盒子是空的,如果快速找到哪个盒子有铁球呢.且小明可以在$O(1)$的时间内知道一段连续盒子的总重量.

这一个非常简单的分治的题目.

可以采用如下的方法来做:

TODO

1. 文字
2. 动画

区间二分性质

现有分割方法如下: m=(l+r)/2 -> new_left = [l,m],new_right = [m+1,r]

想一想

现有分割方法如下: m=(l+r)/2 -> new_left = [l,m],new_right = [m,r]

最后会无限分割到长度为1吗,也就是会出现无限的递归吗?