树的数据结构基本都是依赖二分法来实现的

1.什么是二分法查找

顾名思义就是对数据一分为二 ,然后再为二直到查到数据为准

前提

需要对数据先进行排序(排序也会消耗一些性能), 可以从小到大排 也可以从大到小排, 这个具体看业务需求

查询过程

假设已将数据正序排列 数据为[1,3,4,6,7,8,10,11]
而我们需要查找的是8
第一步数据一分为2
part1 [1,3,4,6] ,part2[7,8,10,11]
用8跟两部分数据的最大或者最小值比较. 8>6 所以数据在part2中
接下来再对part2进行二分 分为part2_1[7,8]跟part2_2[10,11]
继续比较,定位到part2_1中就找到了8

2.二分法的优缺点

二分法相比于正常的从头查询, 来说 有些情况会很快, 比如数据量很大 上万, 你从头开始查询 肯定是没有不断除2来的快,虽然排序会耗费一定时间, 但是是一劳永逸的, 之后查就会快, 而之后设计出的树基本上都是为了达到二分法的速度