数据结构学习笔记四（二分查找）

一、什么是二分查找

二分查找针对的是一个有序的数据集合，每次都通过更区间的中间元素做对比，将要查找的区间缩小为原来的一半，直到找到要查找的元素，或者区间被缩小为0。其时间复杂度为O(logn)。

二、二分查找应用场景的局限性

1.二分查找依赖的是顺序表结构（即数组）

二分查找需要按照下标来随机访问元素。二分查找只能用在顺序表来存储的数据结构上，如果数据是通过其他数据结构存储的，则无法使用二分查找。

2.二分查找针对的是有序数据

二分查找要求数据时有序的。如果数据没有序，可以先排序。如果我们针对的是一组静态数据，没有频繁的插入，删除，我们可以进行一次排序，多次二分查找。这样排序的成本就被分摊，二分查找的边际成本就会比较低。但是如果数据集合有频繁的插入和删除操作，要使用二分查找，在每次二分查找前都要先进行排序。针对珍重动态数据集合，维护有序的成本很高。

二分查找只能用在插入，删除不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适应。

3.数据量太小不适合二分查找

如果要处理的数据量很小，完全没有必要使用二分查找，顺序查找就够了。但是有一个例外，如果数据之间的比较操作比较耗时，不管数据量大小，都推荐使用二分查找。（比如数组中存储的都是长度超过300的字符串，如此长的两个字符串进行比较就非常耗时，此时使用二分查找可以减少比较次数，提高性能）

4.数据量太大也不适合二分查找

二分查找需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。如果太大的数据用数组存储就比较吃力了（开辟不出连续空间），也就不能用二分查找了。

三、二分查找的适用范围

凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找数。实际上，求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势明显。而用其他数据结构，比如散列表、二叉树就比较难实现了。

四、二叉树的变种

1.查找第一个值等于给定值的元素

2.查找最后一个值等于给定值的元素

3.查找第一个大于等于给定值的元素

4.查找最后一个小于等于给定值的元素

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!