2021-05-25 数据结构排序专题【1】： 顺序查找and二分查找（是个人就能想到的最朴素的查找方法）

顺序查找：

无序表以及有序表

二分查找：

问题：顺序查找虽然能够减少有序表的查找次数，但无法降低其数量级，有没有能够降低有序表查找数量级的方法？

1.顺序查找

思维理解：顾名思义，如果要在一个包里找出你想要的东西，这个包不是透明的，怎么找？那就是把东西一个又一个拿出来，找到了，就停，没找到继续。这是我们找东西最朴素的做法。

只不过如果想得更细的话，查找的过程中会分离成无序表和有序表两种情况。如果包里没这个东西呢？无序表那就是不由分说的一通乱找，直到看完了包里的所有东西，才能确定你要找的在不在包里。而有序表则不同，只要按照顺序，查找到了比目标大的数，那么就可以停止，不必再继续找了。

算法代码实现：

逐个遍历

2.二分查找

离开了最朴素的方法，我们试着去思考，有没有更快捷的方法，来帮助我们找到目标对象呢？

对于细分的两种情况，我们发现有无序表和有序表两种。先从比较容易入手的情况开始，有序表。前面我们讲到了有序表在查到了想要的目标后可以停止，如果目标不存在列表内，当读到比目标大的数时，就可以停止，其实这个过程本身是节约了查找次数。那么从查找次数入手，我们把这个单次次数扩大为一种规模的减少。那就有个想法，二分查找。

直接从一个列表的中间开始查找，如果中间正好对于目标对象，则可以停止。如果不是，则将中间的数与目标对象比较大小，如果大了，查前面；如果小了，查后半部分。接下来继续使用二分法，直到找到为止。

代码实现：

法一：指针

PS:学习一下这里的用first 和last标记，以及缩小范围的方法

法二：思考，能不能把代码写得更加简洁？二分查找其本质上就是个缩小问题规模量的问题，直到列表的长度变为0为止

递归

最小结束条件：

列表长度变为0，不存在任何元素

代码实现：

其他思考:

二分查找在时间复杂度上优于顺序查找，但是对数据项进行排序也是很大的开销，需要权衡是否值得。